ID:42290   Apr 28 2008, 6:50 pm Keywords: demo, math This month I bring you... another method of creating random maps! This one could be especially useful if you're thinking about entering the BYOBG contest (http://www.byond.com/members/ DreamMakers?command=view_post&post=41489). Let's skip the small talk. This demo is based on Voronoi diagrams. If you want to know what those are, take a look here: http://en.wikipedia.org/wiki/Voronoi_diagram And here's the demo: http://www.byond.com/members/DreamMakers/files/ gughunter.2008%2D0428/voronoi_src.zip As the article demonstrates, all you need to build a Voronoi diagram is a bunch of seed points scattered around a plane. Once you have that, you just look at every other non-seed point on the plane and figure out which seed it's closest to. Of course this could take a while, since a plane contains an infinite number of points. But a BYOND map is made of turfs, not points, so the job is a lot easier. Or it would be -- except I didn't do it that way! Instead, I allowed the seed points to expand at the same rate. This is a pretty unscientific method, since the regions only grow one at a time, so the regions that grow first get any turfs that are equidistant from two or more seeds. Fortunately, this demo isn't about being scientific, but only about creating a viable random map. The demo offers two basic methods of placing seed points. The first is a grid, in which the seeds are spaced in an orderly manner. This would create pretty dull maps, though, if that was all there was to it; you'd always end up with a uniform bunch of rectangles. So the grid method adds a little gimmick: you get to choose the probability that any given grid point won't get a seed. If you choose a reasonable number, you end up with something that looks kind of like a real city -- the grid is interrupted by irregular regions here and there. The second method is to place the seeds entirely randomly. This creates much more organic-feeling maps, akin to the game board in Risk. The demo also creates a nice little body of water for you, by picking a base region and wandering around the adjoining regions, filling them with water as it goes. You may be able to think of other applications. Here are some to get you started: * Unknown Person, who got a sneak preview, noted "Personally, I don't know what I'd do with it, but it looks like something I'd use if I wanted to make a random anthill." I thought that was a pretty nifty remark, since one of the very first computer games I ever wrote, back in the early 1980's, was called "Anthill" and a little Voronoia might have done it good. * You could try the old party trick known as "reversing figure and ground." Instead of seeing the borders as streets, what if they're walls? You could create a vast cavern network by digging out some doorways. * You could give the regions more interesting shapes by randomly joining some of them together before you draw the borders. * As the Wikipedia entry notes, a Voronoi diagram was famously used to analyze an outbreak of cholera in London (the book "The Ghost Map" tells this story, and is a good quick read). Perhaps you could make an interesting game by keeping the Voronoi diagram hidden, and requiring players to find clues to track down the seed points. Suddenly, without warning, the article ended!
 #1 Apr 28 2008, 6:55 pm A hub entry could be beneficial. That way, the demo could be installed or removed like anything else on BYOND. Also, it would show up in the My Hub section of the pager.
 #2 Apr 28 2008, 7:16 pm Hmm, you make a fair argument. I'm going to bed in just a moment, but I'll make a note to add a Hub entry tomorrow. Thanks!
 #3 Apr 29 2008, 4:27 am (Edited on Apr 29 2008, 8:33 am) I quickly (and I mean quickly) slapped together a Voronoi diagram generator in Delphi. Click on the white space to place a node, (or click the random button to place a few) and then click the generate button. It's pretty slow (using a brute force algorithm) but it works OK for generating low node count images to see what effect nodes in different places have. http://www.byond.com/members/Hazman/files/Voronoi.exe
 #4 Apr 29 2008, 7:22 am (Edited on Apr 29 2008, 8:23 am) POV-Ray uses something similar to Voronoi diagrams for its crackle pattern. I've always felt this had a lot of potential for random synthesis but I've been slow to discover a lot of good uses for it.
 #5 Apr 29 2008, 7:34 am Hazman, here's a technique for improving your algorithm to find the nearest neighbor: 1) Start with a target area covering the whole plane. Define this with a maximum distance, and min/max x/y. For starters the max distance can be width+height of the plane. 2) Pick a random seed within the target area. 3a) If the seed is in the target area but outside of the max-distance circle, mark it invalid; do not include it in future selections. 3b) If the seed is just on the max-distance circle, make note of it; it is also a closest seed. Do not include this point in future selections. 3c) Discard any previously noted closest seed; this is the new closest seed. Set maximum distance to exactly this seed's distance from the target. The new min/max x/y values are constricted so they are now within ±d of your point, where d is the new max distance. Do not include this point in future selections. 4) Repeat step 2 until no more points remain to be selected. You should be able to sort seeds by x, then y, so it's relatively easy to cull invalid seeds quickly. In fact you can simply re-sort as you go along.
 #6 Apr 29 2008, 8:23 am Cheers, I'll update the generator tomorrow at school.
 #7 Apr 29 2008, 8:59 am I have some code demonstrating my idea but I can't post it in comments, so it's on the forum instead: http://www.byond.com/developer/forum?id=634360
 #8 Apr 29 2008, 1:54 pm I got the following error when using the demo: Infinite loop suspected--switching proc to background. If it is not an infinite loop, either do 'set background=1' or set world.loop_checks=0. proc name: vorBuildLand (/proc/vorBuildLand) usr: ACWraith (/mob) src: null call stack: vorBuildLand() ACWraith (/mob): testland()
 #9 Apr 29 2008, 2:35 pm It looks like an initialization problem. I can create land on a clear map, but not on a previously created grid or land. PS: I found the hub entry.
 #10 Apr 30 2008, 12:51 am can you please tell me how you learned to code if its a special class or somthing like that please i need to now i want to make a game but i need to know how to code please tell me how
 #11 Apr 30 2008, 6:49 am Xileft wrote: can you please tell me how you learned to code if its a special class or somthing like that please i need to now i want to make a game but i need to know how to code please tell me how Check out this link: http://www.byond.com/members/ DreamMakers?command=view_post&post=40355
 #12 Apr 30 2008, 6:51 am ACWraith wrote: It looks like an initialization problem. I can create land on a clear map, but not on a previously created grid or land. Ah, good point. I should set it up to be reusable within a single instance of a world. I'll make a note of it. Thanks!