Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Generating fantasy maps – an interactive exploration

mewo2.com

Post reply on HN
Print view View original

41–50 of 65 posts

Re: Show HN: Generating fantasy maps – an interactive exploration

#41

Post by phasmantistes »

douche wrote: post #40
phasmantistes wrote: post #39

Earlier quoted context omitted.

The OP actually cites that project as the method they use for initial polygon generation, and tells everyone to go read it.

If you want to lose a few weeks hacking away at something kind of fun, then turn around and try to implement the Fortune's Algorithm[1] Voronoi region/Delauney Triangulation method that underlies Amit's map generator. Somewhere I have a WinForms app I built a while back that animates the process and draws everything out step by step. [1] https://en.wikipedia.org/wiki/Fortune%27s_algorithm

This is actually what I did in my first internship -- generating Delaunay triangulations (or more often, tetrahedralizations) of points, and then adjusting the underlying sets of points to help ensure that the corresponding Voronoi cells have good properties (generally reasonable surface area to volume ratios).

We didn't use Fortune's for historical reasons (the first versions of the code were in Fortran 77, and written well before he published his paper). Instead we generated triangulations and then flipped edges until they were Delaunay, and then used the corresponding Voronoi diagram. It turns out that flipping edges to produce a nicer triangulation is reasonable in two dimensions, but intractable in 3D and up.

Re: Show HN: Generating fantasy maps – an interactive exploration

#42

Post by fapjacks »

I found this entire post to be completely awesome, but laughed in particular with this line: "I have a programmer's superstitions about always using powers of 2, which are more pleasing to the spirit of the machine." Also, I share similar fond memories of those maps from cheap, grocery store fantasy books!

Re: Show HN: Generating fantasy maps – an interactive exploration

#43

Post by Animats »

Cute. Usually this is done with fractals, as with VistaPro and its successors. You generate a coarse random height field, then subdivide, making smaller random changes locally, until you have all the detail you want.

An ambitious project: take in fantasy novels and extract location cues from them, then draw a map. Find text which mentions a place, then try to recognize phrases which express distance and direction.

Re: Show HN: Generating fantasy maps – an interactive exploration

#45

Post by algorias »

The tricky task of label placement could be outsourced to a SAT solver.

The way it works is that for every city, town etc you generate a few placement candidates (4 positions around the point like you do seems fine) and then calculate all the pairs of placements that collide. For each collision you add a clause to a SAT formula that forbids this combination from occurring. Every solution of this formula will be a clean labeling of your map.

Re: Show HN: Generating fantasy maps – an interactive exploration

#46

Post by klipt »

algorias wrote: post #45

The tricky task of label placement could be outsourced to a SAT solver. The way it works is that for every city, town etc you generate a few placement candidates (4 positions around the point like you do seems fine) and then calculate all the pairs of placements that collide. For each collision you add a clause to a SAT formula that forbids this combination from occurring. Every solution of this formula will be a cle…

That seems like a way of changing a nice, convex problem into a much harder to solve NP-complete problem...

Re: Show HN: Generating fantasy maps – an interactive exploration

#48

Post by haldean »

_qwfv wrote: post #28
quantumhobbit wrote: post #25

Earlier quoted context omitted.

Reamde was the book if any are interested. A cool part was one of the engineers complaining when a powerful user cast a spell that deformed the landscape. The whole world was a huge finite element simulation so that one spell cause CPU usage to spike as whole world had to be updated. The book was fun, sort of a thriller, but I felt Stephenson could have done more exploring the world of the MMO game. A rare complaint…

Cast in another light, it was standard Stephenson fare -- the first half of the book explores a topic deeply and interestingly, then the second half basically sets it aside to trail off into some weird no-man's land. Seveneves was particularly obvious version of this issue.

I thought Seveneves was more like two "first half of Stephenson novels" smushed together; I found myself wishing there was more exploration of the "second" world. I thought the cultural evolution stuff was super interesting.

Re: Show HN: Generating fantasy maps – an interactive exploration

#49

Post by algorias »

klipt wrote: post #46
algorias wrote: post #45

The tricky task of label placement could be outsourced to a SAT solver. The way it works is that for every city, town etc you generate a few placement candidates (4 positions around the point like you do seems fine) and then calculate all the pairs of placements that collide. For each collision you add a clause to a SAT formula that forbids this combination from occurring. Every solution of this formula will be a cle…

That seems like a way of changing a nice, convex problem into a much harder to solve NP-complete problem...

I think you underestimate how hard the original problem is. Small decisions can cascade and have effects very far away on the map. Also, in what exact sense do you mean convex?

Furthermore, SAT is hard in theory but the kind of very structured instances found in practice tend to respond well to heuristics.

Re: Show HN: Generating fantasy maps – an interactive exploration

#50

Post by bovermyer »

mewo2, I am immensely grateful to you for devoting the time and energy to a task I've been meaning to undertake (and thus value), but have yet to find the time.

Your success is inspiring, and I've forked your repo(s) to try and continue your work. Thank you so much!

Post reply on HN