About AI Path Planning in Neon Chrome


Internally we’ve called Neon Chrome a “pseudo-realistic indoor top-down shooter”. This means that the game happens inside a building with at least “somewhat believable interior decoration” and “not completely unrealistic floor layouts”. These parameters were set by the gameplay design: Fun gameplay will be the primary goal and the immersive environment a secondary goal. So, in the end, the environment is not realistic but also not complete¬†fantasy either. We also wanted to let the player destroy everything but the heaviest structural walls in the game. These features determined¬†certain requirements for the path planning. The ideas behind the implementation are described below.

In Neon Chrome, path planning is used extensively to help computer-controlled characters to move around and navigate in levels. Our path planning implementation is based on a roadmap that is essentially a set of line segments that are connected to each other. These lines lie in a level in such a way that characters can move along them without colliding with obstacles.

A roadmap must be constructed automatically for each level because all normal levels in Neon Chrome are generated procedurally and will change between different runs. Levels are not excessively large so it is possible to use a simple grid-based method to construct roadmaps.

We start by generating a grid of evenly-spaced points. For each point we check whether a normal-sized character would collide with obstacles if it stood there. The point is added to a roadmap if there would not be a collision. Finally, the points in the roadmap are connected with straight lines to neighboring points if the character could move between those points freely. This is visualized in the figure below.

roadmap1
The white lines visualize the roadmap. It contains several components that are not connected together.

Unfortunately, this method has some problems. In ideal case, all white lines should be connected but as can be seen, the constructed roadmap contains several unconnected components. That is because obstacles in Neon Chrome can have different shapes and their position and rotation can vary freely. To overcome this issue, we allow roadmap points to move a little if their original position is not collision-free. That simple trick can greatly increase the connectivity of the roadmap. This is demonstrated in the next figure.

roadmap2
The roadmap contains only one component. All points are connected.

In Neon Chrome, virtually all obstacles are destroyable which means that also the roadmap must be updated to reflect changes in the environment each time something gets destroyed. Usually players destroy only single items at once but it is possible to make a massive damage and destroy a lot of obstacles, for example, by using explosives. Updating large portions of the roadmap can be time-consuming and cause stuttering to the game. To ensure a smooth gameplay, we spread this computational burden to several frames.

After the roadmap has been constructed, it can be used to find a collision-free path between two arbitrary points. However, characters in Neon Chrome never follow a path retrieved from the roadmap exactly because that would easily look too clumsy. Instead, paths are smoothed which makes them to look much more natural. The following animation shows an example of a soldier walking in a room.

soldier
A walking soldier.

 

Roadmaps are not the only method we use to control the movement of characters. There are some steering forces that affect characters when necessary. For example, characters try to keep some distance from other characters and they also try to avoid fire and grenades they have seen. This is done by using repulsive forces that try to move characters away.

Overall, by using all these different techniques and combining them together we have been able to create quite nice-looking movements for characters in Neon Chrome.

Learn more about Neon Chrome on Steam

One Comment

Comments are closed.