Hacker News new | past | comments | ask | show | jobs | submit login

If you are using a gas rather than a liquid, it is even simpler. Just set a high pressure at the beginning and a low pressure at the end. The gas will automatically follow the steepest part of the pressure gradient.

The static solution can be calculated by solving the Poisson equation. In [1] you can see a small implementation of the idea.

[1] https://simulationcorner.net/maze/




This reminds me of Collaborative Diffusion https://en.wikipedia.org/wiki/Collaborative_diffusion

A classic example is programming the ghosts in pacman to trap the player, which seems to require a sophisticated, collaborative strategy. Instead, a much simpler solution is to make a "pacman smell" diffuse through the maze:

- The cell containing pacman has its "smell" clamped to 1

- Cells containing walls and ghosts have their "smell" clamped to 0

- The "smell" of an empty cell is the average of its neighbours

This way, dumb hill-climbing will move the ghosts along the fastest route to the player. "Collaborative" behaviour emerges from the "smell" being clamped to 0 by ghosts: if a route to the player is already blocked-off by a ghost, those behind will not get any "smell" from that direction, and will take other routes instead; effectively cutting-off all of the escape routes. (I implemented this in Pygame many years ago, and it was no fun to play, since the ghosts were way too smart!)


I never knew there was a proper term for this technique! In the roguelike development community, these are known as "Dijkstra maps", and people use them for all sorts of things. [1] One of the coolest tricks the article describes is the idea of constructing several different Dijkstra maps for a particular game map, and then multiplying them together under certain circumstances to get a net weight for each tile.

1: http://www.roguebasin.com/index.php/The_Incredible_Power_of_...


Some if Buls Berglund's recent videos about waves in mazes made me realize this.

Funnily enough he uploaded a video two hours ago that shows what it looks like.

https://youtu.be/lBLlYmM6tjU


AFAIK this would also work with an incompressible fluid like water if you started the maze fully filled than add a sink at the exit and a source at the entrance. You wouldn't have any bubbles in that case and the current would flow along the solution.


It would be interesting to see what would happen to a fully filled maze if, once you got a steady continuous flow at the entrance and exit, you injected some dye into the water at the maze entrance.


It would have been even more interesting if this was not in the linked video!


Sorry, I didn't explain myself well enough. I mean start with the maze completely filled with water such that there's no pockets of air left, and water pressure is sufficient for water to race through continuously. Then introducing a distinct dye. The difference would be that it would have far less turbulence from splashing/pooling.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: