How to deal with different sized objects in a pathfinding situation?

[usajoy]

I'm working on a game that uses A-star (A*) for path finding but I've come to a point where by I have some objects that are larger than a single grid square.

I'm running on a grid of 16_16px. wall segments are 16_16 and so make a single square impassable. Some of my baddies are 32*32 and so they need to check that a gap is at least 2 grid square wide in order to be able to pass throguh it.

I can't simply make the grid 32_32 as the design requires thin walls (at 16px) and there are a couple of smaller baddies that only take up a single 16_16 square.

How do I implement this mutli-resolution environment? Is A-star still the correct tool to use?

[justinhj]

Hi there

There are a couple of ways you can go about this.

The simplest would be to make two maps for path finding, one at 16x16 (1 grid square) and one with the 32x32 (2 grid squares). Then have your bigger enemies use the different map.

In the case that the map data is very large you may want to do it a more complicated but more memory efficient way. Both enemies can path find on the same map, but use different astar objects for each size. The get_successors function determines where an enemy can move next. What you need to do is check that the enemy has two grid squares above him not one. Since the code requires you to have a current position on the grid you can choose the top left corner of the enemy for that.

[usajoy]

I want to be like Starcraft, like, entity of different sizes can be moved on a map, how get_successors should be expanded?

I hope to have this demo code to learn :)

thanks!

[justinhj]

Hi

I won't write the code for you. If you don't want to write it yourself using two maps is the easiest solution.

[usajoy]

thanks!