Sign in to follow this  
denn1s

Dicewars lands generation algorithm

Recommended Posts

Hello everyone.[left]
[/left]There is a game called DiceWars: [url="http://www.gamedesign.jp/flash/dice/dice.html"]http://www.gamedesig.../dice/dice.html[/url]

I'd like to figure out what algorithm is used to generate "random" but _balanced_ maps (no players have any valuable advantage)

Requirements:
- Field should be tied (no "islands" should be generated)
- Each player's income (amount of dices to be added in the end of turn) should be about the same (+/- couple of units) in the beginning of game
- Each cell should contain 1-8 dices. It's better if all dices spread more or less evenly among player's spots

Thanks

Share this post


Link to post
Share on other sites
Rather than placing dice randomly over cells, first decide how many each player will get. Then place that number of dice randomly in one player's occupied cells. After that, place that number of dice randomly in another player's occupied cells. This ensures that the "income" is balanced, it is already decided before the random number generator comes in.

If you want to further balance the dice evenly (which the game you linked to does [i]not [/i]do at all), use a weighted probability. This can for example be done with an array (or vector, or some similar structure): add each occupied cell [font="Courier New"]10-num_dice[/font] times to the list, and increase a counter by that value. Then generate a random number smaller than the total sum and pick the Nth element in the array.That makes cells already having dice increasingly worse chances of being picked.

Share this post


Link to post
Share on other sites
I didn't really look at the game you linked that long, but when I saw the first map it generated I immediately thought of [url="http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/"]this[/url] article, based on [url="http://simblob.blogspot.com/"]this[/url] blog, about using a Voronoi diagram to generate a terrain. To wit, the area of the map is seeded with a large randomized distribution of points, and the Voronoi diagram is generated. Using [url="http://en.wikipedia.org/wiki/Lloyd"]Lloyd's algorithm[/url], the distribution of the points is iteratively altered to try to reduce clumping and equalize the areas of the Voronoi cells. From there, it seems like it would be relatively easy to start from the center-most cell and grow a randomized blob. The different areas owned by players could be generated by building one blob of size N, then finding a cell that is neighbor to it and building another blob of size N, finding another neighbor, and so on... Basically tacking a bunch of globs together into one contiguous mass. As far as the dice distribution, for that I would go with samoth's suggestion of giving each player a set number of dice, and distributing the dice equally.

Edit: Looking at the linked game more carefully, it seems that it is simply based on a hex-grid, so you could skip the Voronoi map altogether, and just construct the connected blobs on the underlying grid.

Share this post


Link to post
Share on other sites
Honestly, this looks rather heavily like Risk. Why not just use a random number generator against a list of all the spaces? Start with all empty spaces for the map and a list of every player. Generate a number in the range of all the spaces, apply player 1. Take that space out of empty and put it in occupied. Then do a new empty for player 2 until all are occupied. Take the remaining dice players have and randomly apply them to their respective occupied spaces. Look into how Risk can be setup to begin play. It follows a pattern kind of like this. Each player gets to place a piece (in rotation) on the map. You cannot place a piece on another player's space, but you can place one in either an empty space or in one of your own. When all players run out of pieces, game play begins.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this