Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am new to game development and just want to ask for advice. I need to know which path-finding algoritm will be suitable for my scenario:

  1. Units - any shape. But in most cases rectangles of different sizes.
  2. I have random generated maze and destination point or area.
  3. Because of different maze borders not all unit can fit and move to the end.

How to find path from unit to destination area and check that shape can move to this area?

enter image description here

share|improve this question
    
Found also good link: habrahabr.ru/post/166713 lng: russian. –  Evgeny Apr 23 '13 at 20:25
    
Same article but English: aigamedev.com/open/tutorials/clearance-based-pathfinding –  Evgeny Apr 23 '13 at 21:17
add comment

1 Answer 1

up vote 11 down vote accepted

A* is the logical choice. Your main concern is going to be with generating good navigation nodes. The nodes will tell you everything you need to know about how traversable each node is with respect to each unit.

enter image description here

Having size information associated with your nodes will be very helpful to you. In the above, we see a size 1 unit can use any of the nodes.

Where the same map for a size two unit looks pretty different, since all the size 1 areas are also non-traversable:

enter image description here

The above images are from the article "Clearance-based Pathfinding and Hierarchical Annotated A* Search". There are additional implementation details to be found there.

You don't have to implement a fixed grid to keep size information, you can also create nodes that have a 'best fit' approach and fit the largest area possible:

enter image description here

share|improve this answer
2  
wikipedia link just for the sake of completeness, and also a list of variants. –  petervaz Apr 23 '13 at 19:22
1  
If you've got different sized objects that need pathing, you'll have account for two things. Either let them try to path but get stuck, or do collision detection during the path-finding and return no valid path. There are other options but these are the most obvious ones that come to mind. –  UnderscoreZero Apr 23 '13 at 19:52
2  
The first two diagrams are from this article on "Total Clearance Path-Finding" aigamedev.com/open/tutorials/clearance-based-pathfinding –  Pieter Geerkens Apr 23 '13 at 21:03
2  
@PieterGeerkens Thanks! I had a comment with that link, but removed it when I added an answer, and forgot to add the link again. –  Byte56 Apr 23 '13 at 21:04
2  
@Byte56: No need to thank me; just go find one of my posts and upvote it. ;-) –  Pieter Geerkens Apr 23 '13 at 21:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.