I have a world made by Perlin Noise. It's created on the CPU for consistency between several devices (yes, I know it takes time - I have my techniques that make it fast enough).

Now, in my game you play as a fighter-ship-thingy-blob or whatever it's going to be. What matters is that this "thing" that you play as, is placed in the middle of the screen, and moves along with the camera.

The white stuff in my world are walls. The black stuff is freely movable.

Now, as the player moves around he will constantly see "monsters" spawning around him in a circle (a circle that's larger than the screen though). These monsters move inwards and try to collide with the player.

This is the part that's tricky. I want these monsters to constantly spawn, moving towards the player, but avoid walls entirely.

I've added a screenshot below that kind of makes it easier to understand (excuse me for my bad drawing - I was using Paint for this).

enter image description here

In the image above, the following rules apply.

  • The red dot in the middle is the player itself.
  • The light-green rectangle is the boundaries of the screen (in other words, what the player sees). These boundaries move with the player.
  • The blue circle is the spawning circle. At the circumference of this circle, monsters will spawn constantly. This spawncircle moves with the player and the boundaries of the screen.
  • Each monster spawned (shown as yellow triangles) wants to collide with the player.
  • The pink lines shows the path that I want the monsters to move along (or something similar). What matters is that they reach the player without colliding with the walls.

The map itself (the one that is Perlin Noise generated on the CPU) is saved in memory as two-dimensional bit-arrays. A 1 means a wall, and a 0 means an open walkable space. The current tile size is pretty small. I could easily make it a lot larger for increased performance.

I've done some path algorithms before such as A*. I don't think that's entirely optimal here though.

  • \$\begingroup\$ Implement a navigation mesh then use A*. If you just want them to move towards the player, implement target following steering behavior with obstacle avoidance. \$\endgroup\$ – MichaelHouse Nov 7 '12 at 15:49
  • \$\begingroup\$ The real problem, I think, is how to generate a good graph from a procedurally generated map. If you succeed in that, I'd suggest using Dijkstra's rather than A*. Although it's slower, it's generally better in a labyrinth where good heuristics are difficult, and it doesn't look like your graph will be that large anyway. \$\endgroup\$ – Tayacan Nov 7 '12 at 15:58

Interesting problem.

Staring at the picture and thinking about the problem I think a set of feelers might be the way to go.

Feelers Example

What you do is just put a couple vectors (lines or whatever) on each side of the agent and each time step you test if they are in a wall or not. If they are in the wall you steer away from it. So if your touching the right one you need to steer left. As you get closer to the wall ramp up that steering force to get away from it.

As long as the agent can fit between the walls it should be able to steer right on through. You already have the data for the walls and procedurally creating a graph sound like a pain the butt considering your situation.

Mix that steering force with your normal movement and they should be fine. It might need some heavy tweaking (feeler length etc) You can also scale the length of the feelers off of the speed the agent is moving so that the reaction time to steer away from a wall is adequate.

Anyhow, I hope this helps.

Edit: Forgot to add. I know it seems obvious from the picture but thought I would say the feelers are kept aligned to the velocity of the agent.

| improve this answer | |

You can use the fact that there's only one target in your path finding problem.

For example, you give regularly the position of your player to a different thread. That thread calculates a map of distances from the player for each cell in the blue circle. (I would have used a blue square around the green square) Diagonal movement usually count as 1.4 movement cost. Once done, the thread replaces the previous calculated distance map. You don't have to redraw this map too often, according to the player and ennemies speed. Each time an ennemi wants to move, he chooses the cell closest to the player in his neighbourhood according to this distance map.

When the ennemies get very close, you can use a different path finding method.

| improve this answer | |

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.