• 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
sheep19

Pathfinding A* with multiple agents

5 posts in this topic

I have to implement path finding on GPU as a university project. I am going to use A* (I have used it before for solving 8-puzzles)

 

However, I can't think of a way to make it efficient for a single agent. I probably have to simulate multiple agents to get reasonable performance speed-up.

I read somewhere that I should spawn a thread for each agent, which seems reasonable.

 

However, how would the agents avoid each other? The world (2D map) would have to be updated each time one moves (this means that I must have a "central" array where the changes will be written to, which will make performance suffer on a GPU (or not?)). I know this is an AI forum, so the question I am asking is, how can I update each agents position with the least number of updates?

0

Share this post


Link to post
Share on other sites

However, I can't think of a way to make it efficient for a single agent.

 

What do you mean? In terms of the final path generated, A* is perfectly efficient. Are you talking about the problem of stating the algorithm in terms amenable to the GPU?

 

I read somewhere that I should spawn a thread for each agent, which seems reasonable.

 

No, for most applications it's not a reasonable approach and is likely to cause far more problems than it will solve, especially given that you are doing GPU work.

 

On the whole this sounds like a very difficult problem. Recalculating paths to avoid other agents is non-trivial and has spawned several different variations on A* to make it work. A* itself is probably not very suited to GPU acceleration as it's an algorithm that has a lot of stages that depend on reading previous writes. Attempting to solve both these issues in one project is likely to be quite challenging.

1

Share this post


Link to post
Share on other sites

In my experience, for actual game use, I've found that updating the A* search to account for other units is a bad idea.  Doing it in the simple way leads to way too much global information being broadcasted to other agents.  You might be able to do some shenanigans to make it more localized, but then you might as well be doing some sort of steering behavior to make smaller local adjustments anyways.

 

Not sure how much I can help you here with the GPU side of things, but I always use A* just to get the general path and let the agent's steering behaviors take care of the rest.  Occasionally, I use information I've obtained through local observations to help me generate a different path if the one I'm currently using seems bad.

0

Share this post


Link to post
Share on other sites

What do you mean? In terms of the final path generated, A* is perfectly efficient. Are you talking about the problem of stating the algorithm in terms amenable to the GPU?

 

Yes. I meant spawn a GPU thread for calculating the path for each agent. Then it would be necessary to "inform" the other agents (write to GPU global memory). Or could this be avoided sometimes? (read below)

 

I read somewhere that I should spawn a thread for each agent, which seems reasonable.

 

No, for most applications it's not a reasonable approach and is likely to cause far more problems than it will solve, especially given that you are doing GPU work.

 

On the whole this sounds like a very difficult problem. Recalculating paths to avoid other agents is non-trivial and has spawned several different variations on A* to make it work. A* itself is probably not very suited to GPU acceleration as it's an algorithm that has a lot of stages that depend on reading previous writes. Attempting to solve both these issues in one project is likely to be quite challenging.

 

I see. I have talked with the professor and he has told me that it will be enough if I do some measurements (see how it scales with varying number of agents etc) of an already made implementation (there is one on the NVidia website).

 

If I don't manage to get the ready implementation to work, I will make one of my own, even if the performance is going to be bad - I know it's going to be hard to beat the CPU here. I was thinking of some "tricks" to reduce GPU communication, like an agent not sending any data if it's guaranteed that no other agent will be at  a cell at a certain time.

(for example, if there are two agents, the grid is 10x10 and each of them is at the opposite site, there is no chance that after two steps two agents will be at the same cell).

Edited by sheep19
0

Share this post


Link to post
Share on other sites

As I recall the GPUs still make you do a lockstep instruction sequence of 32 data sets in parallel.

 

?? Partial patrallel processing for the step you find adjacents to add to the Open List ??  in 2D thats 8 on a regular grid and 26 candidates for a 3D regular grid

 

You may be able (for a single Agent thread) to employ a HeapQ which will keep your Open list tree best candidates in sequential order in the same memory space. (to be processed in lumps in parallel)  the adding back to the HeapQ unfortunately would have to be sequential

 

A significant part of the A* processing will still be irregular (and lower the pure use of the parallel nature of the GPU alot)

 

You more definitely could  have  A* paths being calculated in parallel for Multiple Independant Objects  (or multiple targets being considered for the same Agent/object)

Edited by wodinoneeye
1

Share this post


Link to post
Share on other sites

There is a lot that you can do to parallelize pathfinding even for a single agent.

 

I would start by considering more basic algorithms than A*, and only incorporating some of A*'s features (prioritized sweeping, a heuristic) as you understand how to do the more basic algorithms in parallel.

 

Conceptual Starting Point #1: Breadth-first search

 

A* is basically a souped-up breadth-first search.  You can do BFS in parallel: Expand all the nodes in a ply in parallel, and synchronize between plys.  Can you do that on the GPU?

 

Conceptual starting point #2: Value Iteration

 

Value Iteration is more general than A* and very easy to parallelize.  In the case of the single-source shortest path problem, it reduces to the following.  A value d(v) is associated to each vertex v; it represents the distance to the goal.  It is initialized,

 

d(goal ) = 0

d(v) = Infinity for all v != goal

 

Then, you simply do the following:

 

d(v) := minu in neighbors(v) [ edge_cost(v,u) + d(u) ]

 

E.g., if vertex v has three neighbors, u1, u2, and u3, then it looks at the three quantities,

 

edge_cost(v, u1) + d(u1)

edge_cost(v, u2) + d(u2)

edge_cost(v, u3) + d(u3)

 

and picks whichever one is smallest.

 

This minimization can be performed in parallel by all vertices.  To do it, a vertex needs only to look at its neighbors' values.  This can be done either in a "Jacobi style" (in which new values are written to a separate buffer, and buffers are swapped at the end of the iteration -- this is the classic Value Iteration), or in a "Gauss-Seidel style" (in which new values are written "in-place" back to the original buffer -- sometimes called "Asynchronous dynamic programming").  The point is that you have a great deal of flexibility in the order in which you do these updates, while still guaranteeing convergence.  Dijkstra's algorithm and A* are "just" very, very careful optimizations of this basic iteration, first to avoid updating nodes that don't need updates, and then to bias the updates in the direction of the goal (while making certain guarantees).

 

Detail: Bidirectional search

 

Shortest path problems can be solved more quickly by bidirectional search.  At the very least, you can perform these two searches in parallel (though this is more of "cpu-level parallelism" than "gpu-level parallelism").

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