Sign in to follow this  
ianmclean0001

simple path finding

Recommended Posts

ianmclean0001    100
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;
     bool Add;
     int Counter = 1;
     
     while(CurrentWayPoint!=TargetWayPoint)
     {
        
        if(Counter>=waypoints.size())
        break;                                   
                                           
        Add = false;
        ShortestDistance = 1000;                                   
        for(int i = 0; i < waypoints[CurrentWayPoint].ADJACENT_POINTS.size(); i++)
        {
                
                int AdjPoint = waypoints[CurrentWayPoint].ADJACENT_POINTS[i];
                
                if(AdjPoint==TargetWayPoint)
                {
                path.push_back(TargetWayPoint);                          
                break;
                }
                
                ChildDistance = CalculateDistance(TragetX,TragetY, waypoints[AdjPoint].WAYPOINT_X , waypoints[AdjPoint].WAYPOINT_Y );
                
                if(ChildDistance<ShortestDistance)
                {
                
                       ShortestDistance = ChildDistance;
                       ChildWayPoint = AdjPoint;
                       Add = true;        
                
                }
        
        }
        
        
        
        if(Add)
        {
          path.push_back(ChildWayPoint); 
          LastChildWayPoint = CurrentWayPoint;
          CurrentWayPoint =  ChildWayPoint;   
        }
        
        ++Counter;
                                    
     }
    
}

Share this post


Link to post
Share on other sites
spek    1240
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 your nodes. Each node has a (3D) position to start with. Later on you can add more info if you like.
- 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 this post


Link to post
Share on other sites
Codeka    1239
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 this post


Link to post
Share on other sites
spek    1240
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 this post


Link to post
Share on other sites
jwezorek    2663
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[i];
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]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this