Best pathfinding for a 2D world made by CPU Perlin Noise, with random start- and destinationpoints?
- by Mathias Lykkegaard Lorenzen
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).
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.
