Hi, all of you AI experts !!! I was hoping that I can get a lot of feedbacks from my posting here.. so here it goes ! I''m trying to implement AI pathfinding for my games, the thing is that I''m trying to make my waypoints automatically generated based on a grid system. This step I''ve succeded so far, but then I''m trying to implement a pathfinding algorithm. I''m stuck at the fact in a grid like waypoints the distance for each node/waypoints is usually the same, that way I can''t find the shortest path algorithm or trying to make the minimum spanning tree (relaxation of my graph). I''m kinda new on this matter (pathfinding stuffs) and still researching on new things everyday, can somebody enlighten me ?? I saw that half life/counter strike using a grid like waypoints, what kinda pathfinding/shortest path algorithm it used ?? Or making the waypoints automatically generated is not an option so that I have to make my own level editor to create my waypoints manually ?? Ny infos on what I must learn will be great.. Thanks

quote: Original post by yanuart
I''m stuck at the fact in a grid like waypoints the distance for each node/waypoints is usually the same,

I suspect that you''re not looking at your grid in the right manner.

Consider any two nodes in your grid. There are usually many different routes you can take to pass between these two nodes. Some of them will only go along a low number of paths (edges) between nodes, others will pass through many other nodes (and hence travel along many edges between the nodes). If you assign a cost to travelling between any two nodes based on the distance between them, or some measure of resources expended to traverse that edge, then you should be able to see that there are some paths that have a lower cost than others.

So, in the first instance, just use the distance as a measure of cost. Later you might want to weight the cost based on the terrain type, or its slope.

As for an algorithm to perform pathfinding. There are many, since given the grid and a starting point, you can create a tree structure based on next nodes to travel to, assign costs and then perform a search on this tree to find a particular path (i.e., lowest cost that gets to the goal).

Some algorithms for you to check out (there are plenty of resources online, both at this sight and on the net in general): Dijkstra''s algorithm, A*, Distance Transform Algorithm.

Cheers,

Timkin

In A* alg., how do you make (or based on what) your heuristic function ??
I assume that the heuristic function is based on how far are you from the destination, but in an environment/map where it consist of walls and doors it''s not about just drawing a straight lines isn''t it ??

Actually in my A* algo, the heuristic is just that. A straight line from the current node to the goal. There are others, but it works for me.


- Free Your Mind -

Your heuristic should be an estimate of the cost in whatever units your path cost function has. So, if your path cost is distance, then your heuristic should be a distance estimate. Now, your heuristic should (if you want it to be admissable) underestimate (or at least not overestimate) the actual cost to get to the goal from the given node. An easy to compute distance heuristic is the straight line distance, since the actual distance will never be less than this.

Does this make sense?

Cheers,

Timkin

Hmm.. sorry but I''m still confused about the terms overestimate and underestimate.. what does that mean in making the heuristic function ??
If I want to add the terrain type in the cost calculation should I put it in my heuristic function too ?
Does any of you have a good articles/knowledge domain on how to add some strategic pathfinding system in the A* alg ??
I just want my alg can do some clever stuff instead of finding the shortest path..
Thanks.. and forgive me for my insufficient knowledge..

Hmm.. sorry but I''m still confused about the terms overestimate and underestimate.. what does that mean in making the heuristic function ??
If I want to add the terrain type in the cost calculation should I put it in my heuristic function too ?
Does any of you have a good articles/knowledge domain on how to add some strategic pathfinding system in the A* alg ??
I just want my alg can do some clever stuff instead of finding the shortest path..
Thanks.. and forgive me for my insufficient knowledge..

Overestimate means that the heuristic returns a cost that is higher than the actual cost. Underestimate means the oppoiste (that the returned cost is less than the actual cost). The meaning of cost depends on the implementation. In its most simple form, it represents distance. In a more complex model, different terrain types might have different costs.

The job of a heuristic in the A* algorithm is to guess how costly it is to get from the current position to the destination. Since the search is looking for a path and has not yet found one, the heuristic is only able to guess at the actual cost.

To add in different terrain types with different costs is fairly simple. There are only two additions that would need to be done (and really one of them could be much simplified without many consequences). First, when calculating the current cost from the start node to the current node, instead of merely adding 1 to the cost, add the weight of the current terrain tile to the running total. Second (and this can be left out), instead of calculating the estimated cost as the shortest distance, use Bresenham''s line drawing algorithm to generate a list of locations between the current node and the destination node, and add the cost of the terrain type at equal distances along the line (probably use a sampling distance equal to the size of the grid). However, that is not always guaranteed to underestimate. A much simpler replacement for the second change would be to simple take the average weight of all terrain types and multiply that by the distance.

"The Requested Information Is Unknown Or Classified" -Anonymous

Thanks Extrarius for taking the time to answer yanuart''s questions regarding meaning.

yanuart, might I suggest that if you are not sure as to the meaning of a word, try a dictionary before asking here. You''ll get a much faster result! If you don''t have one at home, there are plenty of online dictionaries. For example, Merriam-Webster, or OED.

Furthermore, I highly recommend you read the articles on pathfinding in the Articles & Resources pages of this website (the link is at the tip of this page in the banner). You''ll find most of your questions answered there.

Regards,

Timkin