Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

ageny6

A*

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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!"

Share this post


Link to post
Share on other sites
I''d like to point out that A* is specifically optimized to not do unnecessary checking if your heuristic is a slight underestimate of the real cost of moving to your goal. If you have squares that don''t have the same cost, the A* algorithm will search along those squares that have a low cost first, unless the path gets expensive or of it''s very much in the wrong direction. The heuristic''s task is to guide A* towards its target, and therefore it reduces the space searched unless it has to search the absolutely longest path possible between obstacles.

Also you can make many other optimizations. You can have different landmasses, in order to disable attempts to move land units over water. You can also calculate one path for a group of units that are supposed to move along. And of course, you can use precalculated waypoints to save even more CPU cycles.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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...

There is no spoon

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
For such dynamic and context sensitive landscape, its better to use a pathing heuristic then. If the landscape changes as much as you say, how can the path the AI computed last frame be even valid beyond a couple of frames.

So instead just encode the AI with some simple pathing behaviors like move toward the target, and always turn right when someone is occulding etc.. and when it really gets stuck. Path only far enough away to get closer to the target and out of the obstacle.

It will take much longer for your agents to find their way to the target, but its a good compromise within such an enviroment and your CPU load will be managable.

If however the terrain doesnt change as much. Generate a course map, use that to path for a general path. When the agent encounters a obstacle in its path, it then recomputes a segment of that path around the obstacle but still tries to maintain itself on the original path. When it recomputes a path segment it uses the high resoultion map, and not the course map.

Good Luck!

-ddn

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!