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

A* pathfinding around axis-aligned rectangle obstacles

8 posts in this topic

Hi, I'm faced with the following problem: I'd like to pathfind from point A to point B around various axis-aligned rectangle obstacles. However, I can't preprocess the area to improve performance. The only thing I'm given to pathfind on is the list of obstacle rectangles, and the start and end points (because the rectangles change constantly). It seems that all paths from A to B go through either A, B, or a rectangle corner point, so it seems like I can use A* from A to B on a visibility graph determined by those 3 types of points. However, I am uncertain about how to process the rectangles in a quick fashion to get this graph; there can be up to about 200 rectangles on screen at any given time, and calculating whether each point is directly reachable from every other point results in a very noticeable delay for the pathfinding. Is there a fast way to go about pathfinding through this?
0

Share this post


Link to post
Share on other sites

One solution would be to have a 2D grid of cells covering your entire play area, and use each cell as an A* node. When it's time to do a pathfind it should be pretty easy to work out which cells are blocked due to being underneath one of your axis aligned rectangles.

 

The only tricky bit is getting the resolution of your grid good enough that you strike a decent balance between having far too many cells to do the pathfind quickly, and having too few so that small gaps are missed.

0

Share this post


Link to post
Share on other sites

It looks like you implement only certain part of the whole pathfinding ? That is not a good idea, since it seems like the redesign of the problem is due, but you can only propose the change (and not enforce it).

 

What happens if you break down those 200 rectangles into actual nodes and set them as non-walkable ? I'd start with that.

0

Share this post


Link to post
Share on other sites
 

One solution would be to have a 2D grid of cells covering your entire play area, and use each cell as an A* node. When it's time to do a pathfind it should be pretty easy to work out which cells are blocked due to being underneath one of your axis aligned rectangles.
 
The only tricky bit is getting the resolution of your grid good enough that you strike a decent balance between having far too many cells to do the pathfind quickly, and having too few so that small gaps are missed.

 

Hmm, this sounds like a fairly easy solution. But it would be ideal to have the path have as few turns or joints as possible, as each time I make a turn, I have to stop for a split second. Making very small moves and then moving in another direction will probably make traversing the path take a very long time; is there a way in which I can smooth out the path after finding it?

 

It looks like you implement only certain part of the whole pathfinding ? That is not a good idea, since it seems like the redesign of the problem is due, but you can only propose the change (and not enforce it).
 
What happens if you break down those 200 rectangles into actual nodes and set them as non-walkable ? I'd start with that.

 

Unfortunately, due to certain circumstances, I can't change anything about the problem I've been given, only the way in which I choose to solve it. I'm not sure what you mean by breaking down rectangles into nodes and setting them as non-walkable?
0

Share this post


Link to post
Share on other sites
  1. Treat each corner, your starting position and the destination as nodes (= 802 nodes).
  2. select the starting position
  3. find all nodes in direct sight of the current position and add them to the open-list
  4. while finding the nodes you should also calculate their price (distance + H) (and perform regular A* stuff - add current node as previous if unvisited or cheaper)
  5. jump to cheapest node on the open-list and goto step 3) if this is not the destination.

Since all the rectangles are axis aligned ray tracing shouldn't make that big of an impact, as long as you only move one step at a time (don't calculate the connections between all 802 nodes, only calculate the connections between your current position and all other 801 nodes) assuming you only need 10 steps from end to end, that's ~ 10*801 as compared to 802^2 as I suspect you are doing.

 

Also don't use a grid. The 802 nodes are the ones you should use smile.png

Edited by VildNinja
0

Share this post


Link to post
Share on other sites

You could try to use the method that Mercenaries 2: World in Flames shipped with, that works rather badly in a 3d game, but would work nicely it sounds in your situation. It involves no preprocessing or building of data. 

 

It's basically just an A* search with the nodes determined dynamically.

  1. Push the start position to the open list
  2. Grab next best node from the open list(using normal g and h costs)
  3. Shape cast from the node position to the goal position, if there is a direct open path, you are done, walk the path back to the start to build your path.
  4. If you hit a rectangle, push only the silouette corners on the side of the rectangle that might be visible to the current node
  5. loop

This technique works pretty well in 2d and might be worth considering for your needs. The idea is that every iteration of the search tries to see if the next best open node can go straight at the goal. In situations that the start and end have direct line of sight, it completes with a straight line path right away. Otherwise it functions by finding its way around objects by exploring silouette corners of the object. Works best if the object is convex but technically not required if you have a way to quickly determine what corners are 'visible' from some relative position. 

 

 

All that said, it sounds as though your rectangles change a lot, in which case it may not be recommended to even do pathfinding. If you have a situation where rectangles are moving all about dynamically constantly I would perhaps advise against doing typical pathfinding because it will likely require you to run it constantly to compensate for an ever changing obstacle set. I would potentially consider doing a more influence map style approach where you can update a gridded weighting of the obstacle set with influences and simplify your agent pathfinding to just following the influences, though this technique depends on other aspect of your requirements that you haven't mentioned yet, such as whether there can be multiple destinations, how large the environment is, how many agents may be active and needing to pathfind at once, etc.

0

Share this post


Link to post
Share on other sites
Hmm, it certainly sounds like I can reduce the running time by calculating connections while pathfinding rather than before, as you guys said.

Perhaps I should have mentioned some more details: the player character walks around a 2D area with rectangle obstacles that don't move (or rather, very few obstacles are able to move around, and they're always player-sized or smaller, so if we collide with something, we can just run the pathfinding again). The reason why I said that the rectangles move around a lot is that the player can only see a certain area of the map (which is huge), and because the player is constantly moving whenever it paths around, rectangles move around, get placed in the area of sight, fall out of the area of sight, etc, all the time. However, while pathfinding, they're definitely mostly stationary. The player is the only agent that needs to pathfind. Also, when I pathfind, I'm only looking to go from the starting point to wherever I want to go to, no more. The environment to path in is typically medium-sized (I know that's a poor description but I'm not sure how else to explain it). Also, the rectangle obstacles are allowed to overlap each other, which I hope will not affect the algorithm (at least, it doesn't seem to me like it should affect a great deal).

There's also something else I should have added. Sometimes, it's not possible to find a path from A to B (ie, when B is inside an obstacle or enclosed by rectangle obstacles). Would I have to search through all points, then?
1

Share this post


Link to post
Share on other sites

It sounds like the rectangles are only dynamic in the sense that they come in and out of some active set due to proximity. Even if the world is huge I would definitely still calculate the static navigation of the world and split it into tiles if you really need to only load a subset of the data. I think that in the context of a 2d game, even with a huge world, I would likely still load the entire worlds worth of 2d navigation, which should be pretty small. Even with the full data set loaded in, it shouldn't adversely affect pathfinding very much if basically all the player movement is all done in close proximity to the start point. In other words i would suggest that I doubt its worth the trouble to chunk the navigation up. Not only does it simplify things, but it leaves open the possibility to pathfind with A.I., or to implement a minimap or path 'plotter' as some rpg games have, to lead you to the next objectives, etc.

 

The cost of shape casts in the technique I describe is going to be slower than using prebuilt navigation. It's sole benefit is that it doesn't have any preprocessing requirements, but the runtime cost is more than you would get out of a preprocessed navigation mesh. Do you have an example of the size world and density of obstacles you are targeting?

 

I'm actually using a couple 2d open source libraries to do my real time obstacle baking in a 3d game http://www.youtube.com/watch?v=UhSNwaTV3II&feature=youtu.be

 

Going on the information you have mentioned so far, and assuming c++, if I was going to build navigation for a huge 2d environment I would probably use the exact same libraries.

http://www.angusj.com/delphi/clipper.php

https://code.google.com/p/polypartition/

 

With these 2 libraries, you can use a single gigantic rectangular polygon the size of your world, and then feed all the obstacle rectangles in to boolean them from the rectangle, which would provide you with a set of polygons that are then input into the polypartition to generate optimal convex regions. I think you would be surprised how optimal such a resulting mesh would be. It's fast enough to build to update at load time and small enough that you can easily keep the navigation set resident all the time. It even supports polygon offsetting, allowing you to automatically build navigation sets for variable sized entities.

0

Share this post


Link to post
Share on other sites
I see. Those two libraries would certainly help a great deal; they're probably optimized well beyond anything I could ever manage. Unfortunately, the game world's density can vary immensely. You might be trapped in a complicated maze and have to pathfind out, or you could be in a wide open area with a few obstacles lying around; it has to perform well on all test cases. I suppose I could also keep a record of places I've gone to and what their navigation mesh is to improve performance as well. In any case, I think those libraries' functionalities should be sufficient to generate a good graph to pathfind on. Thanks!
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