Algorithm help

Bengt Richter bokr at oz.net
Tue Jan 28 10:51:40 CET 2003


On Mon, 27 Jan 2003 18:22:17 -0700, VanL <vlindberg at verio.net> wrote:

>Hello,
>
>I am trying to create an internal representation of a maze in python.   
>My first thought was to have a dict, with the keys being ordered pairs, 
>and the values being 1 (wall) or 0 (no wall).  That way I could pretty 
>efficently construct a graph that I could search for the solution.
>
>However, the map description file is in a little different format than I 
>expected -- I had thought that they were going to give us a file with a 
>bunch of 1s and 0s.  However, what I actually will get is a list of 
>lists of ordered pairs:
>
>POINTS=[200,20 200,200 210,200 210,20]
>POINTS=[320,20 320,200 330,200 330,20]
>
That doesn't say enough. Ie.e, is that a path for a U-shaped wall or is it
an enclosed island inside a maze area? How is the outside perimiter specified.
Is the problem to get from one coordinate to another by shortest path? Any path?
Measuraing how?

>I am inclined to still go with the same representation, but I am trying 
>to find a way to efficiently solve the above as an inequality, to get 
>every integer point within the wall.  Does anyone know a good algorithm 
>for doing so?
>
>
>Alternatively, can anyone suggest a better internal representation?
>
One that includes more info ;-)

Regards,
Bengt Richter




More information about the Python-list mailing list