0
\$\begingroup\$

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

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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. :) \$\endgroup\$
    – DMGregory
    Commented Jan 13, 2019 at 13:49
  • \$\begingroup\$ @DMgregory, your comment should be an answer \$\endgroup\$
    – Pliny
    Commented Jan 13, 2019 at 17:19
  • \$\begingroup\$ 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. \$\endgroup\$
    – DMGregory
    Commented Jan 13, 2019 at 17:26
  • \$\begingroup\$ 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 \$\endgroup\$ Commented Jan 14, 2019 at 3:53

1 Answer 1

1
\$\begingroup\$

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? :)

\$\endgroup\$
3
  • \$\begingroup\$ 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 \$\endgroup\$ Commented Jan 14, 2019 at 5:46
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jan 14, 2019 at 5:50
  • \$\begingroup\$ 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. \$\endgroup\$
    – DMGregory
    Commented Jan 14, 2019 at 12:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .