I am using the A * algorithm for my game, it is a kind of Isometric map with lots of tiles. If all the game objects are trees, rocks, houses and only one game object is a moving hero, the A * algorithm works well because then all objects are objects static except for my hero. I use a function: Check_Block (i, j) where i is the row and j is the column of the map. This function will return false if at that location there is a rock or house or tree, etc. But if there are many heroes moving together, I will not be able to use this function because the heroes are not in position permanent.

I have a solution if the hero is in a certain cell, Map [i] [j] = Hero. But if there are many heroes in the same box, I think this solution no longer good. Can someone show me a solution?


Your issue is that you are over complicating your requirements.

If a hero occupies a cell, then the cell is blocked. Do not allow "hero" objects to occupy the same cell. A* only cares if the cell is blocked or not, so all you need to do is tell it if the cell is walkable.

Whenever a hero moves(changes cell), update your grid. Mark it's previous position(cell) in the grid as clear, and mark it's new position(cell) as blocked.

Allow the "hero" objects to store their own position in the grid.

Once all positions are updated, compute new paths for all "hero" objects.

Your algorithm should be as follows:

for hero: heroes loop
    grid[hero position] = clear
    hero update position
    grid[hero position] = blocked
end loop

for hero: heroes loop
    compute A* path for hero
end loop

The A* algorithm does not care what is in the cell; Only if it is blocked, or clear.

What constitutes blocked or clear is up to you. You could decide that any number of heroes can occupy the same cell, in which case, a cell with another hero in it, is traversible to other heroes. This has nothing to do with A*, but is part of your game rules.

  • \$\begingroup\$ Thank you, but in some games, I see a "Cell" that can hold up to 2 or more objects, whether you have any solution to improve A * for this. If done the usual way, each cell can only contain 1 object. \$\endgroup\$ – Traistorm Dec 3 '19 at 2:09
  • \$\begingroup\$ @Traistorm care to provide an example? \$\endgroup\$ – badunius Dec 3 '19 at 8:03
  • \$\begingroup\$ If you play Age of empires 1, you can see two villager can stand on the same "Cell". \$\endgroup\$ – Traistorm Dec 3 '19 at 10:03
  • \$\begingroup\$ I have an idea, which is to create a two-dimensional array, the elements of the array are std :: vector, they contain a list of objects that are above them. But when objects move from cell to cell, I have to delete them from the old cell to the new cell, I can do it, but my method is quite complicated and confusing. \$\endgroup\$ – Traistorm Dec 3 '19 at 10:03
  • \$\begingroup\$ @Traistorm in answer to your first comment: Your rules as to what constitutes an "occupied" cell or not is entirely up to you. All the A* algorithm cares about is whether the cell is clear(traversible) or not(occupied). You could write a function that pulls the contents of the cell, and decides if it is traversible. \$\endgroup\$ – Ian Young Dec 3 '19 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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