Algorithm help

[Andrew Henshaw]

VanL 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]
> 
> 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?
>
If your coordinates can describe arbitrarily-angled line segments, then
I would look at the Bresenham line algorithm.  Given your statement of the
problem, however, I would suspect that your maze has only vertical and 
horizontal walls.  In that case, I'd just check coordinate pairs and step
through the axis that changes.

> 
> Alternatively, can anyone suggest a better internal representation?
> 

Hard to say from your description.  You might want to consider a 
two-dimensional array of bytes; in which case, you will probably want the 
Numeric module (search google).

> Thanks,
> 
> VanL

Andy