0

I am currently developing a game in unity and I was wondering how to solve the following problem.

I have a character on a 2d map which can move up to x meters distance per turn. I want to be able to be able to display the area he can possibly move into on the 2d map.

This is simple to solve if the map is empty, I simply draw a circle around the character with the radius being x. The problem becomes more tricky if there are obstacles in the way, for instance there might be a tree or hill that the character cannot traverse through. I need to be able to calculate the max distance around the obstacles as well.

Initially I was thinking of using a flood fill algorithm (DFS) to calculate the possible places the character could be but this seems prone to inaccuracy if I use too coarse spacing between points and would be computationally expensive if too fine. The obstacle collision areas are represented as a 2d polygon stored as an array of 2d Vector points. I am currently visualizing these on the screen as a red lined 2d polygon. I would like to draw an outline around the character that represents the area that he can reach in a turn but the above solution will always criss cross over the red collision outlines.

I was wondering if there are any other possible approaches that I could take or any optimization/modification of the DFS that could work.

Jkh2
  • 1,010
  • 1
  • 13
  • 25

1 Answers1

0

  1. create 2D map

    • I assume you already have it
    • it should be 2D array (bitmap like)
    • empty space and walls/obstacles should have specific colors

  2. use A* algorithm

    • like this mine A* implementation
    • start from point/object of interest
    • just do not fill until the end
    • instead stop after N cycles (moves)
    • this will give you map of possible destinations per N-moves

  3. visualize back

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380