# Ensure a path always exists between moving objects

I am working on a small non-discrete game where monster are coming towards player in random direction, sort of the very simple asteroid shooter game.

Monster behaviour is as follows:

• they spawn out of screen
• have a final direction
• have a final velocity
• moves in a continuous (non-discrete) way
• they do not stop for any reason nor do they collide together

Note that all of these points can definitely be changed if if might help tackle the issue.

It kind of works, but I sometimes face a situation where player is doomed: monsters are popping in such a way that it is impossible for player to find a way out.

I would like to get rid of this frustration by, upon generating a new monster, ensuring there will always be a way out for the player. Point is that it does not, to me, looks like an simple static pathfinding-like problem, since:

• I just have to make sure a solution exist (maybe easier than finding one ?)
• Objects are moving
• Objects and player can collide

Note: I am not looking for any type of cooked solution, just some references to existing algorithms, implementations,... to look into by myself.

I understand this fairly looks like collision prediction, but what I am looking for is a solution in which a path exists without such collision, which might be a slightly different problem, at least new developers in the domain such as myself...

edit: Generating monsters in a random-like direction seems OK to me, as long as it does not feel like the pattern is "static" and they all can be avoided by following always that same pattern.

• You may find this previous Q&A interesting: How to make obstacles spawn randomly but still leave a way for the player to pass? That thread is about a very constrained situation like Frogger/Crossy Road, but many of the strategies generalize, especially if you extend the path planning problem through time, so you're doing pathfinding in a 3D grid of spacetime instead of a 2D grid of space alone. Commented Oct 26, 2023 at 22:23
• Can you tell us anything about the mechanics of your game (eg. is it discrete/tile-based, or continuous)? Telling us a bit about the way your monsters move would also help. Do they keep one fixed velocity set at spawn time, or can they change direction or pause and continue according to some rules? Commented Oct 26, 2023 at 22:25
• Thanks for your meaningful questions and sorry for the lack of information, I am fairly new and can not imagine which information is worth to be expressed. I edited to define a bit more (continuous, monsters have fixed velocity and direction, can not pause,... yet, but it might be a thing if that can help tackle the issue) Commented Oct 26, 2023 at 22:33

## 1 Answer

Note: I am not looking for any type of cooked solution, just some references to existing algorithms, implementations,... to look into by myself.

A noteworthy algorithm here is Velocity_obstacle.

Its evolved version algorithm RVO(Reciprocal Velocity Obstacles) and ORCA(Optimal Reciprocal Collision Avoidance) are standard solutions for dynamic group obstacle avoidance. In this particular case, only the player can move freely, so the simple original version will suffice.

When spawning a new monster:

1. For each all Monster(B), Get a VO area about Player(A). Combine all VO areas to get the velocity value space that the player can survive.
2. Randomly select a point in the value space as a prediction of the player's velocity. If the value space is empty, the player has no chance to survive at this time. This is due to improper operation of the player rather than the sudden appearance of monsters.
3. Randomly choose a position for the new monster.
4. For Player(B), Get a VO area about NewMonster(A). If the value space does is empty, return to step 3, else randomly select a point in the value space as the new monster's velocity. If you want to increase the pressure, choose a point closer to the VO area.
5. Expand the player's radius when calculating to increase error tolerance.