3 ms·
This reminds me of Collaborative Diffusion https://en.wikipedia.org/wiki/Collaborative_diffusion https://en.wikipedia.org/wiki/Collaborative_diffusion A classi
by chriswarbo 4y ago
This reminds me of Collaborative Diffusion https://en.wikipedia.org/wiki/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!)
- mhink 4y agoI 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_Dijkstra_Maps http://www.roguebasin.com/index.php/The_Incredible_Power_of_...