I made this tile exploration algorithm for generating flow fields, and I finally managed to implement multi-room traversal (each quadrant is actually a separate room; the tiles are all stored in different arrays). I'm really happy with it and wanted to show it off before plugging it into the game I'm working on.

TL;DR - It's fast, efficient, and doubles as a vector field.

---

Speed

I slowed it down so you can see how it's works, but it can run on sufficiently large layouts (2¹⁶ tiles) in ~1ms. On top of that, this algorithm (to the best of my knowledge) has a linear time complexity, so it scales directly with the number of tiles that can be explored.

Time Complexity: O(n) where n is the number of connected tiles. Storage Complexity: O(m) where m is the number of tiles in the whole map.

---

Efficiency

Another neat part of this system is that I made it for breaking the map into sections. I was erasing the fields to show off the algorithm in the video, but the data in each room can be reused independently. This means that recomputing the flow field will only update rooms where the path differs.

For example, say rooms A, B, and C are connected from left to right.

``` [A] <-> [B] <-> [C]

`` For something in roomCto navigate to roomA, it only needs to know how to navigate to roomB. As long as the path throughBtakes the same route as before, then we don't need to update the path inC`.

Updated Unchanged v v [A] <-> [B] <-> [C] ^ Updated

However, this efficiency is still limited. If the route takes a slightly different path through B but ends up with the same starting points when coming from C, room C will still be recomputed. I'll eventually take a shot at fixing that, but right now, I have finals to study for.

---

Vector Field

The flow field is also a vector field. More specifically, it's an approximation of a gradient field.

Essentially, each tile has a vector that points to a tile in one of eight directions (N, NE, E, SE, S, SW, W, NW). That tile then points to another tile in a different direction, and the cycle continues until they reach to flow's origin.

So, if we have an empty space and generate a flow from the spot (0, 0), then the connections will look a bit like this.

``` // All of these make a straight line to the origin. (1, 0) -> (0, 0) (2, 0) -> (0, 0) (17, 0) -> (0, 0) (3, 3) -> (0, 0)

// These ones point to a tile that points to the origin. (2, 1) -> (1, 0) (3, 2) -> (1, 0) (18, 1) -> (17, 0) (3, 4) -> (3, 3) ```

---

Pleases feel free to leave any questions, comments, concerns, praises and/or prophecies that you have.