A Brief Search Review

Two particularly simple algorithms used to search a 2D space include the depth-first search and breadth-first search.

The depth-first search starts at a point and begins traversing the graph. The algorithm tracks one path, advancing it until the target is reached or there are no movement options available. If there are no movement options, the search backs up the path until there is a neighboring node for the path to traverse. Eventually, it will traverse the entire graph, finding the destination in the process. The path, however, is quite long and windy:

The breadth-first search also starts at a point and begins traversing the graph. However, unlike DFS, this algorithm tracks multiple paths, incrementally advancing each until a path reaches the destination. This will return the shortest path between two points, which is great! It will also spend a lot of time looking in the wrong places, which is suboptimal for a search algorithm.

Neither of these algorithms are super great for searching the graph, since they’re inefficient, and DFS doesn’t even guarantee a short path. However, the BFS algorithm traverses the graph in a way that looks how a physical wave would move.

If you want to keep going down the search algorithm rabbit hole, I suggest checking out the Red Blob Games A* introduction.

Breadth-first Waves

A neat affordance of the BFS algorithm is it mimics how physical waves would travel. When a physical wave passes through a slit, for instance, the wave ‘fans out’ and spreads in an arc on the other side of the slit. This is a hugely simplified model for our purposes, but the apparent effects are generally the same.

I know it’s hard to tell, but those are actually two different gifs! They look so similar, it’s hard to distinguish the two.

Sound waves

Applying BFS to sound waves gives us a neat mechanic to play with. As players cause a ruckus, the sounds of their actions can travel semi-realistically and alert NPCs in the area. This adds a nice touch of realism to the AI; if a sound wave hits an NPC, the NPC can react based on the strength and/or direction of that wave. They could investigate what they heard, recognize the sound as gunfire and alert others, etc.

Sound materials

Taking our simplified wave model further, we can apply the idea of acoustic absorption. Essentially, as waves hit or pass through certain materials, we can alter their ‘physical properties’ accordingly. For instance, say you’d like glass to slightly ‘muffle’ the sound:

Here, the ‘glass’ block simply diminishes the wave strength by an arbitrary amount as it passes through. The result is the sound wave ultimately does not travel very far, though it does still pass through - NPCs near the window would still hear something. This is a simple example, but there’s a huge amount of flexibility in these ‘sound materials.’ Properties such as reflection, amplification, and diffraction are trivial to implement.

Waving Goodbye

We examined how the breadth-first search algorithm mimics travel patterns of physical waves. We looked at applying waves as a game mechanic, and potential features and extensions to that mechanic. Sound waves are an easy application, but this mechanic could be applied in a number of ways. Hopefully this gives you a few thoughts and ideas to play with on your own!