# Generate a HexMap where each tile has a different tile on each edge

I’m trying to generate a 7*13 hexmap, with 9 different types of tiles, numbered 0 through 8. I need the map to be randomly generated on each run and it has to be so that each tile has a different numbered tile on each edge.

I’m having trouble with this algorithm. I can generate my map just fine, but there will always be many tiles where they’ll have the same number on multiple sides.

Any tips would be appreciated. Currently, I’m think I’ll have to iterate through the 2d grid, picking my first tile, let’s say 1. And then make sure there is no other 1 spawn in a two block distance. Any better ideas I can use?

Thanks

• This is a problem called Graph Colouring, so you may be able to apply standard algorithms to it. You have a large surplus of tile types (a hex grid is 3-colourable, and you have triple that) so you have a lot of room to deviate from the optimal solutions. :) Jan 13 '19 at 13:49
• @DMgregory, your comment should be an answer Jan 13 '19 at 17:19
• I don't think it's quite enough to stand on its own just yet — it's basically just a link. If I have some time later I'll pitch a more complete method. Off the top of my head I think we can do one scanline-based and one based on permuting a standard colouring. Jan 13 '19 at 17:26
• Thank you for your answer! I'm looking into Graph coloring and edge coloring. I haven't quite grasped how I'll implement it. Just to explain my problem a little better. This is the grid. 9 unique tiles. Each tile should touch a unique tile of all sides (this is the rule to propagate). Image imgur.com/a/QxQhM6R Jan 14 '19 at 3:53

Here's a simple scanline algorithm you can use:

1. Work through your grid row by row: left to right, top to bottom.

2. As you come to each cell, the two cells adjacent above it and the one cell adjacent to its left in the same row have already had tiles assigned. The rest aren't assigned yet, so we won't worry about them.

3. Our three already-assigned neighbours have used at most three of the available tiles (sometimes two, if they alternate A-B-A or at the start of a narrow row, or one for cells at the top & leftmost edges, or zero for the top-left cell)

Mark those tiles forbidden, and count how many tiles you marked. Subtract that from 9 to get the number of options for this cell.

4. Generate a random number i between 0 and this number of options. Take the ith non-forbidden tile from your list and assign it to this cell.

5. Clear the forbidden marking from the tiles used by the left & top-left neighbours and proceed to the next cell.

Since we only ever forbid at most 3 tiles at a time, we always have at least 6 options for the next tile. And because we never place a tile that matches an adjacent tile that's already placed, we're guaranteed to produce a valid colouring with no identical tiles side-by-side.

We only have to read 3 neighbours at each step, and in fact you can exploit the pattern of travel to slim this down even further - the top-right neighbour of this cell is also the top-left neighbour of the next cell, and the cell we just assigned is the left neighbour of the next cell, so we don't need to check them again. Apart from a little set-up at the start of a row, we only actually have to check one new neighbour for each cell we want to assign. How's that for magic? :)

• Thank you @DMGregory. I was trying something different that doesn't seem to work. I wanted to verify what I was doing could work and then make it better so it's pretty brute force right now. There's an array that stores all available tile types for the current tile - this is just int[9] There is a static global array with the x,y dimensions and each tile type in that block. So I started out with finding the pattern on paper - it comes out to making sure that 18 blocks around the center block cannot have the same value (that is what I need). pastebin.com/sPHS49Uy Jan 14 '19 at 5:46
• Was running out of space... So I took that pattern and ran through each line, but now when I run this code, Unity just times out... keep running. And my head's spinning trying to figure out what mess I've made. Jan 14 '19 at 5:50
• Debugging this code is a different problem. Consider investigating it with breakpoints (or The Panic Button if you're on pre-2018) and post a new question describing your investigation so far if you need help solving it. Jan 14 '19 at 12:34