I just, just read the article on A*, and I just can''t seem to picture the algorithm in a more complex environment. That is, say we have 900 units per 900 units map. That 810,000 units to checks for the G and H to calculate the F. That''s way to much processing if the game has to be realtime. What is a man to do? My signature used to suck. But it''s much better now.

Use waypoints. These are hardwired into the system by the programmer. They save computing time imensly. This is much better then using a algorithm like A*. When you use A*, you are calculating the path in realtime. If the path is already hardwired in, it goes much faster.
Hope this helps
BTW, I think Andre LaMothe has some good articles on the subject.

quote:Original post by ageny6
That is, say we have 900 units per 900 units map. That 810,000 units to checks for the G and H to calculate the F. That''s way to much processing if the game has to be realtime.

Huh? Are you saying the map grid is 900x900? That''s not big at all. I don''t understand why you are saying that you would have to do 810,000 checks - one for each map "square". Perhaps I am missing something in how you worded your post.



Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"

Predetermined waypoints will not work with my current project. It's just the way it works out.

Let me formula the question into an example. Say we have player A, which is 900 to the left and 900 units above AI Player B (or AIB). There are lots of obstructions in the way and AIB must attempt to get to Player A. If you have to generate the path from AIB to player A every frame, will the A* algorithm demand a considerable amount of CPU processing?

Sorry for the cheezy question above. Hope this one clears things up.

My signature used to suck. But it's much better now.



[edited by - ageny6 on October 15, 2003 12:49:55 PM]

[edited by - ageny6 on October 15, 2003 12:50:35 PM]

I can understand your situation, i made a comercial RTS game and this was a really hard problem.

Maybe the best way to solve your problem is to adapt others algorithms to your pathfinding process.

What we made to solve this problem is something like this:

1.- Subdivide the map in bigger "Zones", think in this like in an octree (we used Dijkstra's Algorithm to create zones with a determinated number of obstacles). The purpose of this, is to make a pathfinding search in a lower resolution map. (This process must be done in the map initialization)

2.- With this low-res path, create a list of "guide points", this is, create one point in each of the "Zones" touched by your low-res path, and use this to calculate sub-paths in the map (make a short path finding to the next point in the list). One little problem with this, is that your units have to know that this is not his final path, and that it have to calculate the next guide-point, but the advantage is that you reduce your calculations and divide them in smaller process.(this is a process executed by each unit when needed)

This process reduce your memory usage, process time and is really fast to use it with hundreds of units.

Hope this helps

---------------------------------------------
If God with me, Who against me?
Sitio de desarrollo de videojuegos en español
Digital Moon Studio...



[edited by - NeonGE on October 15, 2003 1:31:18 PM]

I understand the concept, but I can''t imagine coding it. At least not for the application I am currently doing. Breaking a specific area into larger zones is almost impossible because the zones always change, and some large zones that may seem impossible or invalid actually are, depending on where you (the player of AI) goes.


How can I determine if are large zone is valid if the validity of the large zone is dependant on manner in which the path in the smaller zone is taken?


Better yet, how do you determine the validity of movement of a large zone?

Thanks

My signature used to suck. But it''s much better now.

An encountered problem is as follows:

The program I am working has as rules that a player can only move up, down, left, or right. No Diagonals. Implementing this concept with the A* algorithm made me think of a case scenario that would yeild an unwanted result (described below). Is this a good anticipation? Or with the A* algorithm simply ignore the problem below even with the movement constraints

Note, the boxes below look REALLY BAD when posted. Click on edit and the small map I want to visually express will be aligned properly.

say we have the following small map:

*----------------*|                ||                ||                ||                ||                ||                |*----------------* 

and we have player A and AI player B:

*----------------*| B              ||                ||                ||                ||             A  ||                |*----------------* 

using the A* pathfinding algorithm, if I understand correctly, A* will give this path as B tries to move to A:

*----------------*| B              ||  *             ||   *            ||    *           ||     ********A  ||                |*----------------* 

Or something of the sort. But, wanting only movements of 90 degrees, the A* algorithm would do something like this:

*----------------*| B              || **             ||  **            ||   **           ||    *********A  ||                |*----------------* 

Which is not what I am looking for (the rather weird diagonal line). Rather, for the project I am currently working on, it would be preferable to generate a path similar to the following:

*----------------*| B************  ||             *  ||             *  ||             *  ||             A  ||                |*----------------* 

How can I modify the A* to prepare such a path? If even possible.

My signature used to suck. But it's much better now.



[edited by - ageny6 on October 15, 2003 10:48:24 PM]

[edited by - ageny6 on October 15, 2003 10:49:12 PM]

[edited by - ageny6 on October 17, 2003 12:32:14 PM]