amitp

Thanks!

It's similar, but the purpose is different. With Lloyd Relaxation you move the Voronoi seed points (input), and then regenerate Voronoi. What I'm doing here is moving the Voronoi vertices (output) from the circumcenters to the centroids. There's no iteration here because the input points don't move. Instead, I am constructing a non-Voronoi tesselation. It has the same structure as the Voronoi cells but the cells do not have the Voronoi property. For my map generator I don't need the Voronoi property; I needed other properties, which the centroid approach seems to give me.

Also check out A* if you want to go 1000 times faster than JPS ;------)

A* does well when it is given a graph of all the decision points that matter. An unweighted grid is full of locations where it doesn't matter — e.g. whether you go N,N,E or E,N,N or N,E,N. JPS searches for better decision points on unweighted grids. There are lots of other A* optimizations for unweighted grids (subgoal graphs, contraction hierarchies, differential heuristics, bucketed priority queues, etc.) — see Table 2 in this paper [1].

JPS is notable for using no precomputation, which is very useful when the map is changing often. If you can afford analyzing the grid ahead of time, you can build a much better graph than using the grid directly — the Tree entry listed in Table 2 takes 30 sec of precomputation to bring A* down to 0.029 ms on average, compared to JPS which takes 62.524 ms on average.

[1] https://www.aaai.org/ocs/index.php/SOCS/SOCS15/paper/view/11...

Glad to hear it! :)

Thank you! I'm working on a new map project using some of those techniques.

It wasn't long ago that Game AI Pro said “bidirectional pathfinding for A* is usually a poor choice”[1]. There's been some recent work presented at GDC 2018 about bidirectional search[2] but even there they said it was only useful sometimes. Have things been changing? I'm not in the industry so I only hear bits and pieces.

[1] Chapter 17 http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter17_Pathf...

[2] Slides https://www.movingai.com/GDC18/GDC18Bidir.pdf or if you have access to the GDC Vault there's a recording of the talk https://www.gdcvault.com/browse/gdc-18/play/1025071/Bidirect...

Also check out the interactive diagrams for the graph search chapter of that book [1]. I especially liked the "shoes of a search agent" one, which emphasizes that the algorithm doesn't "see" the whole graph like a human does.

[1]: http://aimacode.github.io/aima-javascript/3-Solving-Problems...

Cool!

When I read Hawkins's book _On Intelligence_ back in the mid-2000s I had thought it'd be cool to generate music by having the system predict what was novel and what was familiar. By mixing some novel and familiar notes/rhythm/tempo/timbre/percussion into the stream I should be able to make new music from scratch. I was annoyed that so many systems trained blindly on existing music instead of using first principles to generate something (although existing music seems useful for seeding the novelty/familiarity parameters). For games especially it would be nice to turn up or down different types of novelty to match what the player is doing.

However, as often happens, I got distracted before I got there. I learned Pure Data, and then got into audio synthesis, and then got into signal processing, and that led to procedural map generation … :)

I agree, Voronoi diagrams are so much fun! For that map project, at the last minute I switched to something slightly different. The page still says "Voronoi" but the actual demo doesn't use Voronoi. The Voronoi diagram uses the circumcenters of the triangles produced from Delaunay triangulation. I found that for my needs, the centroids worked better ("barycentric dual mesh"). Some comparison pictures here: https://www.redblobgames.com/x/1721-voronoi-alternative/ The graph connectivity is the same but the shapes are rounder.

I've not implemented Fortune's myself. I use the Delaunator library, which maintains all the additional information I wanted in the form of a half-edge triangle mesh: https://github.com/mapbox/delaunator ; Mike Bostock wrote a Voronoi wrapper on top it: https://beta.observablehq.com/@mbostock/the-delaunays-dual

Alternate format: https://threadreaderapp.com/thread/980968298002006016.html

This is my favorite podcast of all time. It's completely fascinating and yet, as with other history podcasts, it puts me to sleep in 5 minutes. I listen to them over and over to catch bits in those 5 minutes.

You get to learn thing like the connections between father/pater/vader and brother/frater/bruder (f/p, th/t/d, b/f), the reason many plurals with 'f' become 'v' (elf/elves, wolf/wolves, half/halves), why 'x' at the beginning of the word sounds like 'z' but in the middle of a word like 'ks'. Or how some languages have more than singular/plural [1]

Unexpected word connection: 'c' in Latin/Spanish to 'h' in English: century/hundred, cornu/horn, casa/house, caliente/hot

Unexpected word connection: 'w' in German-to-English words and 'g' in French-to-English words: warranty/guarantee, warden/guardian (also seen in English/French: William/Guillome, war/guerre)

[1] https://developer.mozilla.org/en-US/docs/Mozilla/Localizatio...

If your goal is to make it "cellular" you can get an even more cellular appearance by using the Delaunay triangle centroids instead of the circumcenters like Voronoi diagrams use. Side by side comparisons https://www.redblobgames.com/x/1721-voronoi-alternative/ (scroll halfway down). The polygons end up looking rounder. I also made a little toy where you can drag an image onto the page to fill a cellular polygon diagram https://www.redblobgames.com/x/1722-delaunay-map-import/ (cartoon images work pretty well but fine detail is lost)

I wanted to thank you not only for this new page but also for your blog and distill.pub, especially the research debt page!

That was one of the five sites I found for eyeglass materials. These are the others:

- http://www.allaboutvision.com/lenses/how-to-choose.htm

- https://web.archive.org/web/20090815102701/http://www.hbutz.... (table at end)

- https://en.wikipedia.org/wiki/Corrective_lens#Ophthalmic_mat...

- https://web.archive.org/web/20160322110111/http://www.optica...

Trivex is impact resistant and lighter but it's also a little thicker than some of the high index materials so the weight ends up being the same. MR-8 was the one I hadn't heard of and was most curious about.

https://www.reddit.com/r/AskReddit/comments/4v3ts4/what_was_... has some notes about scratch resistance

With high index lenses, the chromatic aberration (low "abbe number") was annoying me (see ScottBurson's post), especially on a wide screen monitor. I ended up getting lenses made of glass. But these aren't so great outdoors because you don't want shattered glass in your eye.

I ended up getting glass for use at home at the computer and MR-8 for the rest of the time (hiking, driving). For the computer lenses, I got a slightly lower prescription (-4 instead of -5) and they're a lot more comfortable for reading (people may find these useful after the age of 40). I think next time I'll go for CR-39 instead of glass, as the glass lenses are rather heavy.

The javascript data structures and algorithms are on my new github page:

- https://github.com/redblobgames/dual-mesh/

- https://github.com/redblobgames/mapgen2/

However the html5 UI isn't (it's a big hack I'm abandoning, and working on a different version). Feel free to View Source if you want to see the ugly UI code :)

Glad you liked it! It's still going, with new owners :) I'm revisiting the map generation because the authors of RotMG are working on a new game, and have asked me to work on the maps.

All cool techniques — also see this paper about procedural terrain generation with GANs

https://hal.archives-ouvertes.fr/hal-01583706v2

If you're on a Mac, try Coconut Battery to check the battery health. Mine was showing 30% of original capacity, which explained why it kept draining quickly. Resetting (recalibrating?) it by letting it drain completely and letting it charge got it back up to 80%. I don't know why it had gotten into a bad state :(

I love hexagons too! Hexagon related but not related to the original article:

- http://esolangs.org/wiki/Hexagony - a hexagonal layout programming language, implemented in Ruby, which is also the name a gemstone made of corundum, which crystalizes in hexagonal shapes ;)

- http://hexagons.info/ - "It is likely that HEXAGONS will continue to increase in popularity over the coming years, as humanity enters a glorious new hexagonal golden age, and all sentient beings on our planet ascend to a new, higher state of hexagonal consciousness."

That said, hexagons seem fine for things of the same size (such as the solar cells in the article), but rectangular construction seems to work better for assembling components of varying size (like a house made of rooms of different sizes)…

Yes, it works for me. I'm using the Mitsuharu version. Results: text mode - 6.7ms (SD=0.3); fundamental mode - 6.7ms (SD=0.2); js2 mode - 13.2ms (SD=11.6); org mode - 13.9ms (SD=14.2)

You may find World Machine interesting: http://www.world-machine.com/about.php?page=features

Meshes are used in various kinds of simulation calculations: https://en.wikipedia.org/wiki/Finite_element_method ; there's also discrete exterior calculus: http://brickisland.net/cs177fa12/?cat=5

(I can't get to the site right now) They have a cool implementation that uses es6 generators to interrupt the algorithms as they run, and pass the algorithm state up to the visualization system.

Other algorithm / data structure visualization sites:

- http://will.thimbleby.net/algorithms/doku.php - uses a javascript interpreter that allows the visualizer to show local variables and pause/rewind the algorithm execution

- http://rosulek.github.io/vamonos/demos/ - marks up the algorithm code with line numbers so that it can show how the visualization corresponds to pseudocode

- http://jasonpark.me/AlgorithmVisualizer/

- http://visualgo.net/

- http://www.cs.usfca.edu/~galles/visualization/Algorithms.htm...

- https://illustrated-algorithms-ommzftrylh.now.sh/

For me it was the other way around. The expensive school computer was locked down (this was the mid-1980s) but I learned stuff there that I then explored at home on a home computer. People tried to get into the school computer to capture other people's passwords, so it wasn't a "messing with school computers to make them do new things" as much as a "messing with school computers to prevent other kids from learning anything". I'm glad they were locked down. But I'm also glad my home computer was completely open (Commodore 64, TRS-80, IBM PC) and relatively simple to experiment with. Maybe a Raspberry Pi serves that purpose today but it's so much harder to spend the time to learn that when there's a shiny ipad next to it.

I agree, reverse engineering some of this stuff is hard. I had been studying economics & systems design and put lots of interacting feedback loops into SRE so it's sometimes hard to tease out the individual effects. I've put some notes up here for anyone who wants to clone it http://www-cs-students.stanford.edu/~amitp/Articles/SRE-Desi...

For a quick “where are they now”:

- Barren Realms Elite --> Mehul (my brother) moved from BBS games to web games, with Earth 2025 and then Utopia, and then a web portal Swirve.com, and then he got out of the games business and ran a coffee shop, Dominican Joe in downtown Austin (but it was just sold) - Legend of the Red Dragon --> Seth Robinson (who I finally met this year) moved on to PC games, then mobile games, and now runs a successful MMO called Growtopia (but it was just sold) https://en.wikipedia.org/wiki/Robinson_Technologies - Solar Realms Elite --> I got out of the BBS door world and went to grad school, interested in teaching. I now write interactive tutorials at redblobgames.com, starting with game development but I want to expand into math and computer science. SRE's wikipedia page got wiped by the deletionists http://www.vintagecomputing.com/index.php/archives/922 but was preserved by http://breakintochat.com/

Title's misleading. A* is also 100x faster than A* ;) It depends a lot on the graph you give it.

JPS by itself (not JPS+ in this video) is notable for not requiring any precomputation to achieve some speedup.

If you're willing to precompute some things, there are lots of other techniques available for unweighted grid maps. http://www.cs.du.edu/~sturtevant/papers/GPPC-2014.pdf has an overview of techniques and some benchmarks that use real-world game maps (Baldur's Gate, Dragon Age).

I believe the "goal bounding" from the video is called "arc flags" in the literature.

(Author here) I had been trying to avoid the irregularities for that particular project because the storage of extremely large game maps saves a lot of space if you can use a regular grid instead of an irregular graph. (Certain algorithms like grid distance also run much faster.) If you embrace irregularity you can get some pretty neat maps, like this one from Andy Gainey: http://experilous.com/1/blog/post/procedural-planet-generati...

(Author here) I had been trying to hide the 12 pentagons on the game map but RimWorld stretches the hexagons so that it doesn't have to hide anything. You can see one here: http://steamcommunity.com/sharedfiles/filedetails/?id=823772... Once you build a colony anywhere though, the colony map is square so it doesn't matter if you're on a hexagon tile or a pentagon tile.

HEALpix is cool. It has the same connectivity issue as with all the solutions — some locations are a little different. With hexagons a few polygons are different (polygons); with HEALpix a few vertices are different (three quads instead of four). In games we can get away with not mapping everywhere whereas in astronomy we can't :-)

(Author here) S2 is great (and Eric is brilliant). It uses a cube projection underneath. S2 solves some problems I didn't have (equal area, curve filling) but the main problem I was looking at was the nonuniform connectivity, and as far as I can tell, it's the same with S2 as if you use a cube directly.