• 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.
Sign in to follow this  
Followers 0
Delpee

A* speed

23 posts in this topic

[size=3]Hello GameDevs,[/size]

[size=3]I recently did an implementation of the[b] A* algorithm[/b]. I'm pretty satisfied with the result as this is my first real 'adventure' in the area of AI (I have been programming for about 7 years). The implementation delivers results pretty quick and accurate.[/size]
[size=3]While implementing a question came to mind, [b]how fast is fast?[/b][/size]

[size=3]Here are some images of the implementation in practice:[/size]

[size=3]Agent moving a long distance[/size]
[size=3][img]http://i207.photobucket.com/albums/bb39/Delpeepic/screenshot003edit-1.png[/img][/size]

[size=3]Agent moving through a maze[/size]
[size=3][img]http://i207.photobucket.com/albums/bb39/Delpeepic/screenshot001edit-1.png[/img][/size]

[size=3]Two videos showing the implementation in practice:[/size]
[size=3][url="http://www.youtube.com/watch?v=sUmVLpO9vf8"]Video 1[/url][/size]
[size=3][url="http://www.youtube.com/watch?v=STx6lKIN8SA"]Video 2[/url][/size]

[size=3]To see how fast my implementation worked I did a stresstest. I made the program calculate thousands of paths from random startpoints to random endpoints in my grid. I did this in an empty grid of 40 by 23, an obstacle-filled grid of 40 by 23 and an empty grid of 100 by 100.[/size]
[size=3]These are the results:[/size]
[size=3]40 by 23, no obstacles[/size]
[size=3][img]http://i207.photobucket.com/albums/bb39/Delpeepic/Xtrememode660ppsnoterrain40by23result.png[/img][/size]

[size=3]100 by 100, no obstacles[/size]
[size=3][img]http://i207.photobucket.com/albums/bb39/Delpeepic/Xtrememode360ppseasyterrain100by100result-1.png[/img][/size]

[size=3]40 by 23, difficult terrain[/size]
[size=3][img]http://i207.photobucket.com/albums/bb39/Delpeepic/Xtrememode120ppsdificultterrain40by23result-1.png[/img][/size]

[size=3]Note that I'm mainly concerned about the average calculation time, as you can see, at the 40 by 23 grid with a difficult terrain there is an average calculation time of about 8ms. Also note that I don't have diagonal search, only horizontal and vertical.[/size]

[size=3]My question to the GameDev boards; [b]Is this an acceptable speed, can it be categorized as fast, or slow?[/b][/size]

[size=3]Discuss...[/size]


[size=3]Thanks in advance,[/size]

[size=3]Yuri van Geffen[/size]
0

Share this post


Link to post
Share on other sites
I think you can double the speed on mostly empty areas by spreading from both the start and end and finding the path when the 2 areas collide somewhere, but in a tight maze it might be slower...
1

Share this post


Link to post
Share on other sites
[quote name='Waterlimon' timestamp='1330701966' post='4918617']
I think you can double the speed on mostly empty areas by spreading from both the start and end and finding the path when the 2 areas collide somewhere, but in a tight maze it might be slower...
[/quote]

That is indeed something to think about. In practice though the world is probably not empty (otherwise there is no point to A*), so I don't know if it would make that much of a difference though.
0

Share this post


Link to post
Share on other sites
[quote name='Delpee' timestamp='1330703015' post='4918623']
That is indeed something to think about. In practice though the world is probably not empty (otherwise there is no point to A*), so I don't know if it would make that much of a difference though.
[/quote]

It depends upon the context. For example, the Fallout 3 and New Vegas worlds are by no means empty, but there are still large flat(ish) areas that could bog down A*.
0

Share this post


Link to post
Share on other sites
[quote name='Waterlimon' timestamp='1330701966' post='4918617']
I think you can double the speed on mostly empty areas by spreading from both the start and end and finding the path when the 2 areas collide somewhere, but in a tight maze it might be slower...
[/quote]
You have to be careful with that, as you could easily double your running time too. Imagine the start in the top left corner, and end in the bottom right. The search from the start could go down the bottom and then to the right, while the search from the end could to go the top and then to the left, completely missing each other. You could also have the start and end on a diagonal, but just off by one, and the two searches could go by each other the entire time but just miss each other.

For Dijkstra's, it just might be effective, but for A* I'd be really careful with that.
0

Share this post


Link to post
Share on other sites
Hi, I am pretty new with A*. I have implemented one but somehow I face a weird path of A*. Would you like to help me? Thanks
[img]http://img850.imageshack.us/img850/8779/weirdastarpath.png[/img]
0

Share this post


Link to post
Share on other sites
[quote name='Nemean Charisma' timestamp='1330942956' post='4919406']
Hi, I am pretty new with A*. I have implemented one but somehow I face a weird path of A*. Would you like to help me? Thanks
[/quote]
You should probably start a new thread (so you don't hijack this one) and post some code of what you're doing in your program so people can help you. I'm sure there would be people willing to help :)

@OP: 71ms for a 40x23 map seems like a longish time to me (I know, the average is ~7.8). Was that just a weird burp in the system (i.e. maybe another process was started up that consumed some of the CPU and the OS gave less CPU time slices), or did you see ~71ms more than once?

I'm not sure how fast it compares to professional games, so I can't tell you that. Have you run it with a profiler to find your bottlenecks though?
0

Share this post


Link to post
Share on other sites
[quote name='Cornstalks' timestamp='1330953939' post='4919431']
@OP: 71ms for a 40x23 map seems like a longish time to me (I know, the average is ~7.8). Was that just a weird burp in the system (i.e. maybe another process was started up that consumed some of the CPU and the OS gave less CPU time slices), or did you see ~71ms more than once?
[/quote]
71ms is indeed a long time. I'm not realy sure why, but sometimes the calc-time spikes. Could have something to do with with some other program running at the same time (maybe the snipping tool I used for screenshot?). I'm not realy worrying as the average is way lower. Sometimes it's also way lower then average.

[quote name='Cornstalks' timestamp='1330953939' post='4919431']
I'm not sure how fast it compares to professional games, so I can't tell you that. Have you run it with a profiler to find your bottlenecks though?
[/quote]
Good tip, will do! I will post the results.

I just see the first picture of the stresstest isn't right, replacing it right now!
0

Share this post


Link to post
Share on other sites
I just tested my implementation on a 100x100 randomly generated world (1 in 10 tiles are blocked). After about a second I consistently get a Stack Overflow error. Is this because I use lists to store my closed nodes?
0

Share this post


Link to post
Share on other sites
Not sure about differences in PC's, but my A* implementation finds path on 400x400 maze field that stretches from one corner to another in ~7 msec.
0

Share this post


Link to post
Share on other sites
There are many different reasons why your A* implementation may not perform well. The most common reasons in my experience have typically been:[list=1]
[*]Using the wrong heuristic
[*]Poorly managing the open list (for example, using a slow sort or next-best search)
[*]Having a closed list.
[/list]

Make sure you're using the correct distance approximation heuristic for your map. For 2D tile-based games Manhattan distance is usually a good heuristic.

If you can avoid iterating over the entire open list each time you need to check the next grid cell then do so.

Also, you can optimize away your closed list of cells by instead adding a closed flag to your map for pathfinding. When you start a pathfinding operation you reset the flag on the entire map (you can actually avoid this step by using an integer flag, but that's probably not necessary). Whenever you close a cell, instead of adding the cell to a list, you just set the flag. This will enable you to check if a cell's closed with a simple lookup instead of having to search. This does depend on you being willing to add this flag to your map, which does violate some principles of encapsulation and may offend some of the stricter coders out there. You could instead allocate a separate structure for this maintained by your pathfinder, but you'd have to make sure your structure always matches that of your map. Implementing that separation could be more trouble than it's worth.
0

Share this post


Link to post
Share on other sites
Thanks smr for your response. I think it mainly has to do with the iteration of my closed list. My heuristic is allready calculated Manhattan style. Maybe I could improve the open list a bit, but I surely should get rid of the closed one as everyone is telling me ;).
0

Share this post


Link to post
Share on other sites
OP, probably one of the most overlooked optimizations for a* is that instead of maintaining seperate open and closed "lists", have a 2d array of chars that represent the state of a node (0=n/a, 1=open, 2=closed, 3=unpassable), with a seperate 2d array of uints for important node-specific statistics such as distance travelled.

Another extremely useful optimization is to use binary heaps to sort your open list values. I recall that when I tested the binary heap sort versus the std::list sort, the difference in speed was half an order of magnitude, even when there were very few values in the heap which is one of the binary sorting algorithm's weaknesses.
0

Share this post


Link to post
Share on other sites
[quote name='Delpee' timestamp='1330971871' post='4919525']
[quote name='Cornstalks' timestamp='1330953939' post='4919431']
@OP: 71ms for a 40x23 map seems like a longish time to me (I know, the average is ~7.8). Was that just a weird burp in the system (i.e. maybe another process was started up that consumed some of the CPU and the OS gave less CPU time slices), or did you see ~71ms more than once?
[/quote]
71ms is indeed a long time. I'm not realy sure why, but sometimes the calc-time spikes. Could have something to do with with some other program running at the same time (maybe the snipping tool I used for screenshot?). I'm not realy worrying as the average is way lower. Sometimes it's also way lower then average.

[quote name='Cornstalks' timestamp='1330953939' post='4919431']
I'm not sure how fast it compares to professional games, so I can't tell you that. Have you run it with a profiler to find your bottlenecks though?
[/quote]
Good tip, will do! I will post the results.

I just see the first picture of the stresstest isn't right, replacing it right now!
[/quote]


Excluding the rendering from the recorded time ???

An A* testing app I helped work on years ago had selectable parameter for render every X path steps (was a 512x512 map) along with high performance timers for the actual recorded A* processing time. (heapQ, flags on map etc.. amazing how far its performance we managed to increase)
0

Share this post


Link to post
Share on other sites
[quote name='wodinoneeye' timestamp='1331272457' post='4920587']
Excluding the rendering from the recorded time ???
[/quote]

What I do is get a DateTime.Now before calling the algorithm-function and directly after the function returns the path I take the difference between the old DateTime.Now and the current one. In this way I exclude any other code from the time tracking.
0

Share this post


Link to post
Share on other sites
how are you sorting your open list? pushing/popping items off the list is probably one of the most time consuming aspect's of pathfinding systems. binary heap would speed up most systems 10 fold if your not already using them.
0

Share this post


Link to post
Share on other sites
For comparison, I had an A* implementation that could cover a loosely connected network of ~30k nodes in roughly a millisecond on a Core 2 Quad a couple of years ago (no multithreading involved). I could probably dig up and sanitize the source if you're interested, but it's scary stuff :-)
0

Share this post


Link to post
Share on other sites
I would love to see it, even just as a way to see the differences! Which sorting mechanism did it use?
0

Share this post


Link to post
Share on other sites
I started with a std::priority_queue but ended up writing some custom gibberish (IIRC) by the end. I honestly don't recall clearly.

It's buried on a hard drive on a dormant machine I don't use anymore, so it may be a day or three before I can dig it up. Add another evening or so to sanitize and document it.


If you don't hear back from me relatively soon, feel free to drop me a PM and pester me into doing it, I've been meaning to publish that code for a while :-)
0

Share this post


Link to post
Share on other sites
[quote name='Waterlimon' timestamp='1330701966' post='4918617']
I think you can double the speed on mostly empty areas by spreading from both the start and end and finding the path when the 2 areas collide somewhere, but in a tight maze it might be slower...
[/quote]
This is a good advice for you ,and I am really agree with .
0

Share this post


Link to post
Share on other sites
[quote name='amile duan' timestamp='1331605226' post='4921544']
[quote name='Waterlimon' timestamp='1330701966' post='4918617']
I think you can double the speed on mostly empty areas by spreading from both the start and end and finding the path when the 2 areas collide somewhere, but in a tight maze it might be slower...
[/quote]
This is a good advice for you ,and I am really agree with .
[/quote]
You read my comment about this, right?
0

Share this post


Link to post
Share on other sites
[quote name='amile duan' timestamp='1331605226' post='4921544']
[quote name='Waterlimon' timestamp='1330701966' post='4918617']
I think you can double the speed on mostly empty areas by spreading from both the start and end and finding the path when the 2 areas collide somewhere, but in a tight maze it might be slower...
[/quote]
This is a good advice for you ,and I am really agree with .
[/quote]

I have to agree with cornstalks, on a theoretical principle, it can speed things up, but i expect cornstalk's example of where it would fail's would be common. as well, if it does succeed and follow the same path to meet with the starting search grid, if searching from start to end produces the same path as start/end meeting in the middle, than you have most likly gained nothing.

the only scenario where this is useful imo, is if the end point is blocked from the starting point, in a small room, where the end search would produce that the two nodes are not reachable much quicker than start-end search.
0

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  
Followers 0