• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.

Archived

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

BeanDog

Simple (not really) Pathfinding (yes, again)

30 posts in this topic

OK, I''ve been working on it, but now that I actually time the beast, I find that my method takes over 1/20 of a second per execution for about a 50-square move! This is totally unreasonable. I''ve downloaded someone''s A* demo, but it took a few seconds to do the same job. Precalculated paths would work best, but what about moving obstacles? I really like the region search idea (thanks to whoever had that one). Problem is, once again, moving obstacles. Man, I pray someone has an idea. Just out of curiosity, how do the pros do it? Does anyone know? Maybe a StarCraft or C&C programmer will read this. HEY GUYS, HOW DID YOU MAKE IT WORK THAT FAST??? For goodness sake, this wasn''t even a problem on my 486 playing WarCraft II! I REALLY wish I were on the inside with Blizzard or something ~BenDilts( void );
0

Share this post


Link to post
Share on other sites
What sort of data structures are you using? Your numbers seem extraordinarily bad... how big is your search space?
0

Share this post


Link to post
Share on other sites
I am using a 256x256 grid.
It takes one function call, and about 6 data lookups and 2 small (less than 6 iterations) nested loops to see if a unit can move onto a square.
For those of you who haven''t read my other thread, my search goes straight toward the goal, and when it hits an obstacle it splits into 2, going opposite directions (clockwise vs. counterclockwise) around that and each following obstacle. After a certain # of iterations, whichever search is the closest or hits it first wins, and I save the path into my creature''s class.

~BenDilts( void );
0

Share this post


Link to post
Share on other sites
I still think A* would be better until you have a good idea of what you''re doing. If the version you used took 2 seconds, it wasn''t programmed very well. A* is used by many professionals and is not that slow.

What happens if one of your split paths hits another obstacle? Does it split again? How does it decide to stop going (counter)clockwise around an obstacle? How many separate paths do you usually end up creating each time you search?
0

Share this post


Link to post
Share on other sites
Beandog,

How dense is your environment?

I mean are we talking a desert with the occasional cactus to avoid or are we talking cities with cars moving everywhere?

This can be a decisive factor in which way to go.

If there are few objects to avoid your algorithm is good, but I would consider doing this : reduce the complexity of your environment by setting waypoints. Set a waypoint on every corner of an obstacle and when the waypoints are in a direct line of sight you KNOW you can move from one point to the other. That way you won''t have to do a calculation in each grid. You can simply say when you have to get past a rectangle moving from south to north : Go to the southwest corner of the rect., then to the northwest corner, then to my goal and you''re past the object in 3 calculations instead of at least the pixelsize of the rectangle.

If you work in a dense environment, try setting random waypoints and calculate the easiest way through using Dijkstra or something. Your algorithm will then stop as soon as it finds one way, instead of trying to find the best way, speeding things up.

All the best,


******************************
Stefan Baert

On the day we create intelligence and consciousness, mankind becomes God.
On the day we create intelligence and consciousness, mankind becomes obsolete...
******************************
0

Share this post


Link to post
Share on other sites
Yes, it would split again at every obstacle. Which means, for one large block, it could split over 100 times, because any time it can''t move directly toward the target, it is seen as a new obstacle. However, I keep a grid that tells me which areas have been searched through already and any search hitting it will be stopped.

I usually end up with around 15 for a complicated map, I mean 15 existing when one of them hits the end or my total iteration limit runs out.

This actually works really fast if I set the max iterations to 20, it will find the best path for the next 20 spaces that will put it closest to the goal. However, when I tell it to go for, say, up to 100, or even take all the stops out and go ''till it gets to the end, it is really slow(1/20 sec.)

You must remember I am running on a P-233MMX with 128mb RAM. It''s not the fastest machine in the world.

~BenDilts( void );
0

Share this post


Link to post
Share on other sites
I can''t help with A* optimisation (except to say, get a 1000mhz machine) but for moving obstacles you should think of path-finding on two levels, planning and reactive.
The planning layer is what you have so far, a path from start to goal node in a grid. The reactive layer deals with moving from grid to grid or within a grid (all path finding is grid based, look at AoK or TA and the units seem to be moving on a pixel by pixel level but the world is broken up into grids for path-finding use). The reactive layer could then build small local paths around moving objects which is a lot quicker than it sounds as the number of paths across a grid increases exponentially with the grid size i.e. a 10x10 grid is more than twice as quick to path build for as a 14x14 grid, which contains twice as many blocks but far more potential paths. Reactive layers could also function with different forms of path finding such as wall crawling (bumping into objects and walking along their sides in whichever direction moves you closest to the goal position) or using areas of repulsion originating from the obstacle so that the path finder will tend to take a path around the it.

Actually, considering your A* speed problem you could deal with it by breaking up the processing over several frames, stopping each path plan after X nodes have been expanded or storing common paths / path segements (small CPU overhead for calculating what is common but worth it). Remember, the majority of units will be moving as part of a group from point A to point B, so they have to deal with their own individual reactive layer but their planning layer can, within reason, be identical.

Mike
0

Share this post


Link to post
Share on other sites
I think I''ve got it licked.

When I do pathfinding, I just search every 2 spaces, not each and every one in the path. Chances are this will avoid all the little obstacles, and if not, it will recalculate when it hits one. This process takes only a very small fraction of the time my other way did.

Thanks for the input, guys. Any more ideas are welcome, it''s not perfect.

~BenDilts( void );
0

Share this post


Link to post
Share on other sites
quote:
Original post by BeanDog

I think I''ve got it licked.

When I do pathfinding, I just search every 2 spaces, not each and every one in the path. Chances are this will avoid all the little obstacles, and if not, it will recalculate when it hits one. This process takes only a very small fraction of the time my other way did.

Thanks for the input, guys. Any more ideas are welcome, it''s not perfect.

~BenDilts( void );


From your posts in this thread, I would suspect that your Astar''s poor performance is due to implementation.

I''ve seen 50 step paths found on a 1024x1024 map in 15ms (milliseconds) on a P90 using an Astar.

Here are some optimization suggestions:

1) Make sure the Open List is fast. If you use MSVC++ then consider using the STL priority queue container, and modify it so that you can use an iterator (very easy to do) and then derive your Open List from the new priority queue. It is lightning fast!

2) Use pointers and not the actual nodes. Store your Astar flags for Open/Closed status in the map itself, and then only process using a pointer to the map node.

3) Use the Manhatten Distance for the h() of f() = g() + h().

Starcraft, Age of Empires (and Kings) and virtually every commercial RTS game I can think of use the Astar (or a variant of it). Astar is the best pathfinding algorithm when discreet cells or nodes are available (ie. forming a graph), so before you dismiss it, you may want to make sure you have a good implementation of it. Amit Patel''s web page (available via a link from www.gameai.com is an outstanding source of Astar code).

Good luck,

Eric
0

Share this post


Link to post
Share on other sites
hey hey, what about dijkstra for shortest path? how well does it match up against A*?



cheers,
muffin
0

Share this post


Link to post
Share on other sites
quote:
Original post by cornmuffin

hey hey, what about dijkstra for shortest path? how well does it match up against A*?



cheers,
muffin


My experience with Dijkstra''s algortithm is that it is not as fast as Astar, and it is not guaranteed to find the optimum path (as Astar is when using an admissible estimate - the h() in f() = g() + h()). YMMV.

In fact, an Astar with a zero value for h() is basically the same as a Dijksta''s algorithm.

Eric
0

Share this post


Link to post
Share on other sites
I think Dijkstra always finds the optimal path since it was originally constructed as a way to find the shortest path through a weighted graph.

If you use the corners of polynomal obstacles as nodes in your graph and the distance as the weight on a link, you''ll get the shortest path with Dijkstra.


******************************
Stefan Baert

On the day we create intelligence and consciousness, mankind becomes God.
On the day we create intelligence and consciousness, mankind becomes obsolete...
******************************
0

Share this post


Link to post
Share on other sites
quote:
Original post by StrategicAlliance

I think Dijkstra always finds the optimal path since it was originally constructed as a way to find the shortest path through a weighted graph.

If you use the corners of polynomal obstacles as nodes in your graph and the distance as the weight on a link, you''ll get the shortest path with Dijkstra.




I don''t think Dijkstra''s is guaranteed to find the optimal path (although I have been known to be wrong before). I agree it can find the shortest path, but shortest is not always optimum. Especially in an application like pathfinding on a computer game map with variable terrain costs (think of a road that goes around a mountain as opposed to the path over a mountain; the road path may have overall lower terrain costs - and hence be more optimal - than the overland route directly over the mountain).

Anyway, when one uses Astar, one can simply use the estimate h() as intended (and get Astar pathfinding) or set the h() to zero and get Dijksta as needed by the game.

Eric
0

Share this post


Link to post
Share on other sites
Geta,

I might be wrong as well, so I''m definitely not saying you are, I''m just telling what I think:

Since Dijkstra is a mathematical approach to find the shortest path through a weighted graph, it will always give you the shortest route based on what you use as weights on the interconnections in the graph. So you could use distance between nodes and you would find the shortest path.
You could use travelling speed and then you would find the quickest path. That''s how we saw it in our course of Discrete Math last year, but I don''t know A* well enough to be sure that Dijkstra would always match the result of A*.

Greetz,

******************************
Stefan Baert

On the day we create intelligence and consciousness, mankind becomes God.
On the day we create intelligence and consciousness, mankind becomes obsolete...
******************************
0

Share this post


Link to post
Share on other sites
quote:
Original post by StrategicAlliance

Geta,

I might be wrong as well, so I''m definitely not saying you are, I''m just telling what I think:

Since Dijkstra is a mathematical approach to find the shortest path through a weighted graph, it will always give you the shortest route based on what you use as weights on the interconnections in the graph. So you could use distance between nodes and you would find the shortest path.
You could use travelling speed and then you would find the quickest path. That''s how we saw it in our course of Discrete Math last year, but I don''t know A* well enough to be sure that Dijkstra would always match the result of A*.




Astar is the same type of search algorithm as Dijkstra, "a mathematical approach to find the shortest path through a weighted graph". Astar evolved from an algorithm called "A" which was almost identical to the Dijkstra algorithm. That is why, it is possible for Astar to function like a Dijkstra, by only setting h() to zero.

Possibly of interest to you, is a little tool written by Bryan Stout (called PathDemo), and available in the archieves of the Game Developer Magazine here in the web (sorry I don''t know the exact URL), that visually represents a path search process for a variety of pathfinding techniques. Bryan wrote it in Delphi (or Pascal??) several years ago to support his lecture on pathfinding at the Computer Game Developers Conference. If you can locate that tool, then you may want to experiment with Astar and Dijkstra pathfinding approaches (I think both are included) and you will visually see that Astar will find the optimum path with fewer expanded nodes (hence the fastest) and it is guaranteed to always find the optimum (if the h() is admissable). You can also tweak the parameters and run Astar with h() = 0, and then run a Dijkstra over the same map, and see that with h() == 0, both algorithms will search the same way.

Anyway, I think we have beaten this horse to death, so I will conclude my part of this discussion with a parting comment; that I like both algorithms, and have used them both (in their place) in commercial games.

Eric
0

Share this post


Link to post
Share on other sites
so in an RTS game like starcraft, dijkstra should do well? a path is a path, no weight difference, or else unmovable. also, do i need a heap priority queue, how about just a simple weighted, connected graph, for dijkstra? thanks.

cheers,
muffin
0

Share this post


Link to post
Share on other sites
quote:
Original post by cornmuffin

also, do i need a heap priority queue, how about just a simple weighted, connected graph, for dijkstra


The priority queue and the graph are not interchangable, as they aren''t referring to the same parts of your program. The graph,in this case, is your map, including any passability factors. The priority queue is the effective way of storing the nodes your algorithm generates with their cost, so that when you are generating the paths you can get the next node to examine more quickly.

You don''t -need- a heap implementation of a priority queue. You can just do a linear search through an array to find the next node to use, for example. But using a heap-style priority queue speeds up this process.

0

Share this post


Link to post
Share on other sites
Geta,

Thanks for your replies to my posts! I ran the demo by Bryan Stout and I see the difference indeed.
It''s been an interesting discussion, which shows this board is a great place to hang out and learn.
Thanks!





******************************
Stefan Baert

On the day we create intelligence and consciousness, mankind becomes God.
On the day we create intelligence and consciousness, mankind becomes obsolete...
******************************
0

Share this post


Link to post
Share on other sites
quote:
Original post by StrategicAlliance

Thanks for your replies to my posts! I ran the demo by Bryan Stout and I see the difference indeed.
It''s been an interesting discussion, which shows this board is a great place to hang out and learn.
Thanks!




You are welcome, and learning goes ditto for me too.

Eric
0

Share this post


Link to post
Share on other sites
quote:
Original post by Kylotan

[quote] Original post by cornmuffin

also, do i need a heap priority queue, how about just a simple weighted, connected graph, for dijkstra
(end Original post by cornmuffin)

The priority queue and the graph are not interchangable, as they aren't referring to the same parts of your program. The graph,in this case, is your map, including any passability factors. The priority queue is the effective way of storing the nodes your algorithm generates with their cost, so that when you are generating the paths you can get the next node to examine more quickly.

You don't -need- a heap implementation of a priority queue. You can just do a linear search through an array to find the next node to use, for example. But using a heap-style priority queue speeds up this process.




Kylotan is absolutely right on. And for anyone who happens to develop in MSVC++ or Metroworks, I might suggest that you look into using the Standard Template Library (STL) queue container class for a priority queue. I modified it to be a pathing queue by just adding support for iterators (very easy to do) to the queue class object. It has turned out to be blazingly fast, and extremely easy to work with, as an OPEN list.

Eric


Edited by - Geta on June 20, 2000 11:41:27 AM
0

Share this post


Link to post
Share on other sites
Hi all

I am working to a commercial RTS game like Starcraft and others and i have done a pathfinding algo....

I looks a little like A* but its not

talking about speed i wanna tell u all that i work in ASM so i get the Maximum speed possible and i have a P2/400 /128M
and still a corect fast A* with no lists (for speed i use big matrix) its still too much slow on a 256x256 cell map

So the word is out:

YOU MUST OPTIMIZE IT TO WORK today....

There are many optimizations in doing A* like algo or other alogos and this is all that pros will do...they think and rethink the game they make so they can make outstanding optimizations....

Optimizations makes the difference....

And dont wait for a pro to tell u how he did it....
1.It may not work for u
2.He cant tell u if he wants to make some money

Pros will eventuallu show u the way but they CANT walk it for you

in the end consider what will u make if u have diffrent size units on same map ? eh?

non-pro answer is he will divide the map in 2x2 cells and then he will wonder why his units dont walk like in Starcraft....and sit to such distance one from the other

i have been there....

Bogdan
0

Share this post


Link to post
Share on other sites
PS Beandog

i think u have my RTS demo ...

Check my pathfinding..... its a kinda of A* in my own way and it works at about 50fps is it not?

optimizations do it (not ASM code belive me it was 0,5fps in the start)

Bogdan
0

Share this post


Link to post
Share on other sites
Actually, I don''t have your demo. But I do know what you mean with different sized units on the same map - but I handled it all right. What is the URL to your demo?

PS is it worth it to have a separate thread emptying a pathfinding queue, to keep the game running smooth despite hefty pathfinding? My game runs at a smooth 30 FPS on my P233/128MB/Banshee at 800x600x16bit with the # of pathfindings per frame as it is (by the way, I''ve got most of the kinks worked out, its kinda messy but works fast), but would it be better with multithreading?

PS Please dont start arguing too much about multithreading v. normal procedural stuff. I''ve heard enough of that. In the end, though, Windows does about 50-60 threads at a time anyway, whats another one going to do?
0

Share this post


Link to post
Share on other sites
Well, I think you''ve answered your own question here. If you''ve no problem with the overhead of threads and you''ve got the coding kinks worked out then you can only try it and see.

However, surely windows isn''t running 50-60 threads at the same time your full screen game is playing? I have no idea of the number but I''d imagine it''s not running that many. And have you seen the jerkiness of Windows when it''s running multiple threads and program switching? Not good for a game.

Mike
0

Share this post


Link to post
Share on other sites
quote:
Original post by Geta

And for anyone who happens to develop in MSVC++ or Metroworks, I might suggest that you look into using the Standard Template Library (STL) queue container class for a priority queue. I modified it to be a pathing queue by just adding support for iterators (very easy to do) to the queue class object. It has turned out to be blazingly fast, and extremely easy to work with, as an OPEN list.

Eric



What do you mean, added support for iterators? I keep redoing my pathfinding as I can never seem to get a good balance between clean code and good speed
0

Share this post


Link to post
Share on other sites