# Tree search for path finding - algorithm critiques

So, I'm pretty new to AI in general, and am trying to implement a tree-based search from a textfile input (a maze). An example would be:

``````||||||||||||||||||||||
| ||        | |      |    \
|    |||||| | |||||| |     \
||||||       |    P  |      \
|   .| |||||| || |||||       \  P = Start
| |||| |         |   |       /  . = Goal
|        ||| |||   | |      /
||||||||||    |||||| |     /
|          ||        |    /
||||||||||||||||||||||
``````

I understand the basic algorithms in general (BFS, DFS, A*, etc.), but I want to make sure I'm implementing them correctly, and not somehow cutting corners because "I know where the best path is". My basic idea is:

• Parse the file into a 2D array
• While parsing, if I encounter `P`, note the Start index
• While parsing, if I encounter `.`, note the Goal index
• Begin at `Index(Start)`, and evaluate surrounding [blank] spaces
• Create `Node`s for these, and add the appropriate actions to the current Node's available actions --- Add these `Node`s to my `frontier` que
• [continue whichever algorithm from here]

So I guess my main question is, am I generating my "world" correctly? Is it right to not really create Nodes until I encounter them during the search? It seems wasteful to get to a [blank] space, scan the surrounding 4 directions for other [blank] spaces, and if they exist add them to the available actions and create `Node`s for all possible actions.

Another alternative would be to generate Nodes as I encounter the [blank] spaces, but this would be hard (since I wouldn't be aware of the upcoming blanks) ... should I parse the file completely, and the traverse the stored array to create all possible Nodes/Links/Actions? Or is that considered cheating somehow...

An object-oriented programmer's instinct on this sort of problem is that at some point they'll have to instantiate some sort of `Node` object, but you really don't. You don't even need to create a 2D array.
The path-finding algorithms are described largely in terms of `sets`. You can write very clear implementations by parsing your maze into `sets` of `(row, col)` tuples. This lets you write operations like the following:
``````(row, col) = starts.pop()
Here `starts`, `spaces`, and `goals` are `sets` you created from parsing the file, and `visited` is updated over the course of your algorithm. Note that set operations are generally `O(n)`, where `n` is the smallest operand. That means `neighbors & spaces` will only do `4` comparisons, no matter how many spaces in your maze. It's not the most efficient implementation possible, but it's efficient enough, and the clarity it buys you is well worth it.