Hacker News Reader

Comment by 60654 | Hacker News Reader

Sounds like a classic potential field implementation, and yeah, they're very useful. There are two problems: scaling with map size (large maps or high detail maps), and update cost in action-heavy games (if the field source moves on every frame). But for small roguelikes it's a very good fit.

View on HN

Presumably you could set the fill radius to a maximum corresponding to the largest detection distance possible (for the monsters you have in-game or even in-level)?

There's no point filling an entire level if monsters only react when the player gets within say 30 tiles. Even line of sight should have limits.

You could add something like an A* heuristic on top where monsters are drawn to the general direction of the player based on a vector, but switch to shortest-path when they're close. (but then you worry about getting stuck I guess)

Performance is a serious problem still. Well, if the world needs to be updated often (multiple times a second).

Consider a semi-open map with 30 tiles sides, we're talking a thousand tiles in total and/or paths a hundred tiles long. For the effect to propagate to the 30th tile away, the propagation algorithm has to iterate more than 30 times.

Graph algorithms are generally slow (whole milliseconds on large graphs) but repeated many times over they can get truly horrendous.

One trick is to spread the computation out over time, if you don't need to do it all at at once every frame. Since the enemies don't move that fast, a bit of delay might be good enough, depending on what you're tracking.

SimCity has several layers like pollution, land value, etc, which slowly diffuse over time. But it only does that computation every so often, not every frame. It has a 16 phase simulation clock, and it scans the cells of the map in eight stripes over eight steps, then scans different layers like taxes, traffic and rate of growth decay, power, pollution and land value, police coverage and crime, population density, fire coverage and disasters, and the RCI valves. (That made it possible to run on a C64!)

Chaim Gingold's SimCity Reverse Diagrams show how the different phases of "Simulate()" perform different kinds of analysis over time, and how the different map layers interact with each other.

https://lively-web.org/users/Dan/uploads/SimCityReverseDiagr...

>SimCity reverse diagrams, by Chaim Gingold (2016).

>These reverse diagrams map and translate the rules of a complex simulation program into a form that is more easily digested, embedded, disseminated, and and discussed (Latour 1986).

>If we merge the reverse diagram with an interactive approach—e.g. Bret Victor’s Nile Visualization (Victor 2013), such diagrams could be used generatively, to describe programs, and interactively, to allow rich introspection and manipulation of software.

>Latour, Bruno (1986). “Visualization and cognition”. In: Knowledge and Society 6 (1986), pp. 1– 40.

>Librande, Stone (2010). “One-Page Designs”. Game Developers Conference. 2010.

>Victor, Bret (2013). “Media for Thinking the Unthinkable”. MIT Media Lab, Apr. 4, 2013.

Yeah this is an interesting problem for exploring stuff like recursive/non-recursive code, the overhead of conditional statements when you have to run thousands of them, etc. I've seen some examples online where people claim a few million voxels a second (I've not tested though).

I think this is also how 3D printers work (effectively). They do a form of scan-line filling to minimise the number of jumps between sections of filament.

Thanks for the alternative name! Helps further research the technique. The core idea is relatively simple so I'm not surprised these are known. But finding a name of something you know is not easy with just a search engine.

Sure thing! And as I mentioned in another comment, if you google for "potential fields" and "flow fields" in games, there's a whole bunch of papers and talks on this.

Interesting, because these kinds of potential fields are similar to the "predictive map" representations we see in the firing rates of hippocampal cells.

Now that you mentioned "flow field", I remember seeing it in a Supreme Commander AI demonstration technique. Two columns of tanks can navigate through each other seamlessly, without chaos. And in realtime. Imagine seeing this in the days of Warcraft 1, where it was common for a unit to use left hand rule across the entire map because the bridge was momentarily occupied.

https://www.youtube.com/watch?v=iHuFCnYnP9A

Also get called influence maps

And also called... dynamic programming in some communities. On of the most classical algo, just before the more interesting class of problems where the map size is too big to do it

That's what James Gosling called it in his paper about the Emacs screen redisplay algorithm.

https://news.ycombinator.com/item?id=22849522

https://donhopkins.com/home/archive/emacs/mw/display.c

https://donhopkins.com/home/documents/EmacsRedisplayAlgorith...

7. Acknowledgements

The people who did the real work behind this paper are Mike Kazar, Charles Liescrson and Craig Everhart; all from CMU.

Bibliography

1. Kevin Q. Brown. Dynamic Programming in Computer Science. CMU, February, 1979.

Reply on news.ycombinator.com