I'm trying to learn some pathfinding algorithms, and I'm having trouble converting my map to usable nodes in a tree. My map is very simple, a 2d matrix of 1s (walkable) and 0s (unwalkable), where the 'player' starts at a random starting point and finds the shortest path to a random goal by moving up, down, left, and right. In my mind, this sounds simple enough. Create a node from a the starting coordinate and put it in the open list; move it to the closed list and put its children in the open list, and repeat until the goal node is in the closed list and then move back up the tree to find the path. I may have not gotten exactly right, but I have the general gist of it. However, I'm not sure how to create the nodes and keep track of its children. Supposed 'square' [2][2] is my start. Of course, I know that its children are at [col +1], [col-1], [row + 1], and [row - 1], but how do I create a node from that information that will also know its children? I hope I'm making myself clear... I'm not really sure how to tackle this problem.

Two different parts of the data structure... nodes and edges. And edge connects two nodes. Run with that for a while.

I've just finished implementing something similar (to learn pathfinding algos as well). What I did, and what I believe is a common approach, is to make each node have a reference to its parent. Then when you find the goal node, traverse through the parent of each node until you get back to the start node (you can put this info in a stack of points for a character to follow etc.).

So when you're adding a node, just have it store a reference to the node you're currently expanding (its parent).

It might be useful to think about the pointer being to the predecessor node, rather than the parent. As you find a shorter route to a node, change the predecessor to point to the node you just came from. Then, you iterate from the goal backwards to the start, following the predecessor nodes as you go, building the path.

Quote: Original post by The Orange Peanut
However, I'm not sure how to create the nodes and keep track of its children. Supposed 'square' [2][2] is my start. Of course, I know that its children are at [col +1], [col-1], [row + 1], and [row - 1], but how do I create a node from that information that will also know its children? I hope I'm making myself clear... I'm not really sure how to tackle this problem.

What you are putting on your lists must have coordinate information at least, right? So your nodes would be at least:

class Node {  int x;  int y;}

And then you can just write a method that takes a Node, and returns all of its children.

The fact that all of your 'squares' are in a multi-dimensional array is only useful to you - if you want to path with it using a graph-traversal algorithm, I believe you'll need to store structures containing the coordinates. Your 'square' objects making up the array could store their own coordinates, and you could use that as the node type, for example.

[Edited by - Argus2 on November 30, 2008 8:06:34 PM]

I would suggest making a simple 2d matrix like you have that are booleans or ints of just t/f or 0/1. Now you need to make a vertex (your square class) for every point in that matrix. Give it a name, if it is walkable or not, and the coordinate w/in your matrix. Now when you create edges start at the upper left corner and go through it the same way you always do, (from left to right, and top to bottom). Crate 2 edges for each vertex, these edges have 2 vertices and a weight (of 1). One of these 2 vertices will be the current vertex you are at, and the second will be either to the right or below you (except for the lowest row or last column). Now you have all edges you need, of course you will have to skip vertices that are un-walkable, as well using an algorithm for this is actually a bit hard.
Another route you can take is giving each spot on your matrix an adjacency list.
Lastly I suggest reading Depth First Search, Breadth First Search or Dijkstra's algorithm.
Also generally a tree isn't used as a data type for graphs (The root being your current node and its children being other objects of an edge.