# simple path finding

This topic is 2935 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi there I hope this make sense ;) I am having some trouble with a simple path finding script that I am trying to write. Basically I have a node list (I called them waypoints) each waypoint as a list of adjacent nodes. I have a find path function which takes the current node and the target node. The function looks at the current nodes adjacent node list and tries to find the closest node to the target. It then goes through to process until it finds the target node. I have got the feeling I haven't got the basics of pathfinding right. I have looked at A* pathfinding but the examples I have seen are grid based so I didn't under stand how to apply it to this problem. any help or advice would be really appreciated. Thanks Mac not sure if its worth showing you but here is the FindPath function please forgive my code I am new to C++.
void PathState::FindPath(int CurrentWayPoint,int TargetWayPoint)
{

if(!path.empty())
path.clear();

int TragetX = waypoints[TargetWayPoint].WAYPOINT_X;
int TragetY = waypoints[TargetWayPoint].WAYPOINT_Y;
path.push_back(CurrentWayPoint);

int ChildWayPoint;
int LastChildWayPoint;
int ChildDistance;
int ShortestDistance;
int Counter = 1;

while(CurrentWayPoint!=TargetWayPoint)
{

if(Counter>=waypoints.size())
break;

ShortestDistance = 1000;
for(int i = 0; i < waypoints[CurrentWayPoint].ADJACENT_POINTS.size(); i++)
{

{
path.push_back(TargetWayPoint);
break;
}

if(ChildDistance<ShortestDistance)
{

ShortestDistance = ChildDistance;

}

}

{
path.push_back(ChildWayPoint);
LastChildWayPoint = CurrentWayPoint;
CurrentWayPoint =  ChildWayPoint;
}

++Counter;

}

}


##### Share on other sites
You're on the right track with A*. Examples might show grids, but A* can be applied on anything, including sets of nodes. The only difference is that unlike with the grid, a node can be connected to 1,2..n other nodes. And the distances between them may vary.

You could try this:
<setup>
- Create connections between the nodes. Each node can be connected to 1 or more other nodes. Let the connection store the "cost". Cost would be the distance between node A and B, but it could also include the quality of the path (asphalt versus mud). Plus constraints can be made here. Mark your connection if it requires special skills such as swimming, stair climbing, being not too big, ....

<A*>
Same principe as with the grid. Start at a node and move to all of its connected nodes (if the connection allows). You could store the additional temporary info in the nodes (F, N, H, see http://www.policyalmanac.org/games/aStarTutorial.htm ), add the connected nodes to a list, and repeat the process until you found the target. Then traverse to get the shortest path. Once you can do it on a grid, a nodelist shouldn;t be a problem either.

Rick

##### Share on other sites
If you think about it, a grid is just a special case of node graph. That is, a grid is a node graph where all of the nodes are evenly spaced, and each node connects to exactly four others (except at the edges and if you also count diagonals).

So if you understand how A* works on a grid, generalising it to the case of an arbitrary number of connecting nodes and arbitrary distances between nodes should be relatively straight forward.

Perhaps try to implement A* on a grid first and then think about how it can be generalized as I described above. A* seems complicated when you first encounter it, but once you get that "a-ha!" moment and you understand it, it's actually deceptively simple.

##### Share on other sites
thanks for the help I have started to look at A*
but hoping I wouldn't have to use it. I've never managed to
get my head round it. :)

thanks again

Mac

##### Share on other sites
It will prove to be a valuable lesson. There is a reason why A* is popular :) It's one of the fastes way to find paths, even in mazes. And like Codeka said, it's not that difficult. Check out this applet:
http://thoughtsfrommylife.com/article-720-A*_Pathfinding_Algorithm_Demo_Applet

I bet there are more, so you can see in steps what exactly happens. The only difficult part is maintaining (larger) lists. The link I posted earlier also tells how to make a binary heap I thought.

Rick

##### Share on other sites
If you're having trouble understanding A* you might want to try learning Dijkstra's shortest path algorithm first. A* is basically just a generalization of the Dijkstra algorithm and Dijkstra's algorithm is pretty simple to understand. Here's an implementation of Dijkstra:
struct NodeInfo {    NodeInfo() :         visited(false),         distance(MAX_PATH_DISTANCE),         previous(-1) {}    bool visited;    int distance;    int previous;};void FindPath(int src, int dest, const std::vector<WayPoint>& waypoints, std::list<int>& path) {    std::vector<NodeInfo> nodes(waypoints.size(), NodeInfo());    DistancePriorityQueue queue;    queue.insert(0, src);    nodes[src].distance = 0;    while (!queue.empty() && !nodes[dest].visited) {        int curr_waypoint = queue.getNext();        for(unsigned int i = 0; i < waypoints[curr_waypoint].adj_points.size(); i++) {            int neighbor = waypoints[curr_waypoint].adj_points;            if (! nodes[neighbor].visited) {                int dist_to_neighbor = nodes[curr_waypoint].distance +                    CalculateDistance(waypoints[curr_waypoint].x, waypoints[curr_waypoint].y,                                       waypoints[neighbor].x , waypoints[neighbor].y);                if (dist_to_neighbor < nodes[neighbor].distance) {                    queue.erase(nodes[neighbor].distance, neighbor);                    queue.insert(dist_to_neighbor, neighbor);                    nodes[neighbor].distance = dist_to_neighbor;                    nodes[neighbor].previous = curr_waypoint;                }            }        }        nodes[curr_waypoint].visited = true;    }    // Now build the shortest path from the info in 'previous'    if (nodes[dest].visited) {        int j = dest;        while (j != -1) {            path.push_front(j);            j = nodes[j].previous;        }     }}

I haven't implemented DistancePriorityQueue in the above. What it needs to do is return the WayPoint index associated with the lowest distance when getNext is called and erase that entry. You could implement this data structure with an std::multimap.

[Edited by - jwezorek on February 10, 2010 6:58:32 PM]