3
\$\begingroup\$

I'm creating a top-down space shooter game where there is no real "map" per say since there is no real terrain, but there are obstacles in the form of asteroids, other ships and a few circular structures, but nothing like a maze where an AI would need to find a path to get out of -more like things an AI doesn't want to collide with.

I want my AI to navigate around these objects. However, as you may have guessed, asteroids and ships aren't static, they have a scale and a velocity and can be destroyed. What's the best algorithm/method to use for navigating around moving obstacles in open space?

For context, my AI ships have a waypoint at all times that determines where they want to move to. Basically what I'm asking for is a way to ensure that if an asteroid or other ship were to fly in front of my ships as they fly toward their waypoint that the ship would make some effort to avoid it. Currently they just keep ramming into them and dying :(

Improve this question
\$\endgroup\$
4
  • 2
    \$\begingroup\$ What type of algorithm have you considered so far? \$\endgroup\$
    – Vaillancourt ♦
    Mar 10, 2019 at 18:25
  • \$\begingroup\$ I'd considered A* which is considered the best by many sources, but it seems a bit too powerful for simple obstacle avoidance in open space. Also, it seems to operate on static environments, where the environment in my game is always changing. \$\endgroup\$
    – Agent Tatsu
    Mar 11, 2019 at 23:22
  • \$\begingroup\$ A* may be a good choice even if it's "a bit too poweful" simply because it's faster than other options: it doesn't find the best solution, it finds the first available. On the other hand, if your level environment is dynamic, you may want to take a look at simpler steering behaviours algorithms, such as "chasing", "wandering", and "avoiding", to give the idea of moving around. \$\endgroup\$
    – liggiorgio
    Mar 19, 2019 at 16:17
  • \$\begingroup\$ @liggiorgio's description of A* is not correct. A* is guaranteed to find the best solution - that's what the * in A* means (in the field of discrete optimization, a * is commonly used to designate an optimal solution). The algorithm is structured to ensure it finds and returns the shortest/lowest-cost path to the goal before any longer/more expensive path, so in that sense it does find "the first available" but not in the sense of happenstance or greedy approximation. Its speed comes from its use of a heuristic to prioritize the most promising directions. \$\endgroup\$
    – DMGregory ♦
    Aug 2, 2020 at 2:19

1 Answer 1

Reset to default
1
\$\begingroup\$

You can't reliably create a full path that you can actually follow through completely to your destination since the ships interaction with the world is very unpredictable (physics-simulation is costly to predict and player input mixes everything up anyway).

Path-finding is good to get an route that is valid at that point in time but it can be unstable, something changes and BOOM your path goes the other way around, your ship has to stop and/or turn.

If you rely on path-finding you will need to periodically regenerate the path since in your case a previously valid path isn't guaranteed to stay valid for long when everything moves around. This isn't anything new, other games have to do this too but asteroids is a special case since the whole environment changes continuously.

You need something more dynamic and faster, that's where steering behaviors, like obstacle avoidance, are useful. You can use them stand-alone or in conjunction with path-finding to smooth out the generated path.

Let's say you want to implement obstacle avoidance, first you need to detect and select the obstacles you want to navigate around.

You need to check for them in the flight path of the ship, by basically pre-calculating the future positions of the asteroids and your ship and doing a collision check on all of these extrapolated positions. This is easy for asteroids that simply move in one direction with constant speed, for the others not so much, but an approximation is often enough.

Now when you have predicted a collision you can change your direction accordingly, there are lot's of algorithms out there that you can borrow from, it's up to you.

I recommend you to read up on obstacle avoidance and keep path-finding for later. You will be able to handle many situations by just moving towards your goal and avoiding obstacles on the way there.

Moving around/avoiding obstacles

If you want to use for example A* for pathfinding you could take into account the clearance of the space you want to move through to select paths with less chance of a collision.

Clearance-based Pathfinding

Depending on your requirements vanilla A* might be more than enough.

Improve this answer
\$\endgroup\$

You must log in to answer this question.

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