I'm writing a 2D game where the player has to kill a Ninja. This Ninja is coming closer with a constant speed chasing the player. The Map has some static obstacles like stones no one can pass. The player can move too and has different types of weapons to damage the Ninja in different ways:

  • Laser: instantly on whole range

  • Gun: projectile (circular) following a fixed path

  • Trap: circular floor ability which detonates after time

I want the Ninja to dodge those Weapons the best he can, he is allowed to take some damage, the least is preferred.

I now have different ideas how to achieve that:

  • A* with 3rd dimension (time): This is working but the paths are ugly and post processing is not my favorite. Also the Graph's size is about 1000x1000, making it inefficient (on creating neighbors), i try to reduce node count by scaling the nodes to unit.hitbox (40px), which drastically improves the calcs, but the paths look even more ugly..

  • Theta*: won't work even tho I love it, but line-of-sight on moving obstacles is...

  • Visibility Graph: same as Theta*, moving obstacles...

  • Steering: haven't tried this one yet how it performs with constant speed and moving (, delayed) obstacles

  • Local Avoidance: won't work as the weapon speed is bigger than Ninja movement speed

  • Geometry: tangents, vector projection etc.... could work well if there aren't much obstacles to dodge

Do you have any other ideas how to achieve some good doing for the poor Ninja?

(NINJAS USUALLY DODGE EVERYTHING... That's why I also plan to give the Ninja a Ninja-Roll feature he can use every 10s to dash on some position if he can't dodge something)

Representation of the raw map (little dots are 40px) enter image description here

A* Pathfinding with time dimension and a 5px-Grid

Edit: I'll check out D*-Lite and RRT*-Smart

Edit #2: Both are not what im looking for, i will try to optimize A*

  • \$\begingroup\$ A very raw example of the Ninja + Circular obstacles added to the Question. I usually try on basic representations first to check if its doable. \$\endgroup\$
    – LuaNoob
    Apr 29, 2019 at 15:22
  • \$\begingroup\$ Also added an A* example with time dimension (dynamic weight 1.5 and Graph rounded to 5px instead of 1px for less nodes to explore) \$\endgroup\$
    – LuaNoob
    Apr 29, 2019 at 15:39
  • \$\begingroup\$ Moving projectiles are dropping my FPS hard. I need to reduce the number of obstacles to check to only the most dangerous ones, maybe I use a QuadTree for that purpose or I will pre-compute some things after the cast event, so there's less calcs in the pathfinding. I experienced the nose count exploding from 100 to 3000+ when there are many moving obstacles nearby. \$\endgroup\$
    – LuaNoob
    May 1, 2019 at 23:29

1 Answer 1


I made it :D

Using A* with time dimension. Creating the obstacle paths just one time, on cast. Then i simply do A* and on neighbor check i check for the time the spot would have as well, if a spot is blocked, ignore it.


enter image description here

enter image description here


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .