0
\$\begingroup\$

I'm currently in the middle of writing a game where there is a maze. The maze itself is already drawn ok, and once I have the layout I randomly rotate all the pieces.

I have a 'start' cell that is a different colour to the others,when cells are rotated in such a way that they become 'linked' to this start cell, then all the cells that are linked back to this cell should change colour.The start cell itself can be rotated as well so just because a cell is back in it's initial rotation it doesn't mean it's connected. Also any random cell can be rotated regardless of whether it's neighbour is already connected. E.g if the start cell is at [8,8] in a grid, then all the other cells bar it's immediate neighbours could get connected and then finally the closest neighbours get rotated to form a completely connected grid in which case all cells should change colour like a flood fill.

Are there any good algorithms to solve an issue like this? I was thinking of a flood fill from the start cell every time a cell is rotated somewhere but I'm not sure if this is the optimum way to do this, especially as I have to check what each type of cell is (e.g is it a corner piece, a straight piece, a T Junction or a dead end with only one connecting side) and then check what it's current rotation is compared to it's neighbours rotation and type. Obviously this is fine if you can stop at immediate neighbour to the start piece, but when other sections of the maze might be 'complete' and then an interjoining piece is linked I would need to flood fill all of them. I had started writing this but I found myself just pretty much duplicating switch statements for all the different types of piece and then what type of piece their neighbour was and comparing the rotations of each piece. It felt very 'DRY' even though the comparisons were changing

I'm writing this in swift, but I guess an algorithm would be generic

thanks

Improve this question
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Flood fill, depth-first search, or breadth-first search are pretty much the canonical approaches here. Instead of switch statements though, you might consider defining your pieces in data. Imagine your PieceType struct contains a "Connections" array of enums/vectors identifying the offsets to its connected neighbours in its default orientation. Then your logic can be very uniform: iterate over a piece's connections (transformed by its rotation), and check if there is a piece at that offset that also has a connection back. Your code needn't know what's a "corner" tile at all, that's data's job \$\endgroup\$
    – DMGregory ♦
    Nov 16, 2016 at 22:05
  • \$\begingroup\$ You should leave an answer rather than a comment. Really given me food for thought, though does mean some rewriting! \$\endgroup\$
    – TommyBs
    Nov 17, 2016 at 20:57
  • 1
    \$\begingroup\$ I try to write fairly in-depth answers, which takes some time. So, when I've only got enough time for a quick suggestion, I prefer to put it in a comment, free to expand into an answer if anyone finds the suggestion fruitful. ;) \$\endgroup\$
    – DMGregory ♦
    Nov 17, 2016 at 21:02
  • 1
    \$\begingroup\$ I think this is close to what you are looking for (it is in lua): github.com/hakelimopu/CoronaSDKDev/blob/master/Pipes/… \$\endgroup\$
    – PlayDeezGames
    Nov 18, 2016 at 18:58
  • \$\begingroup\$ Interesting they use a sprite frame rather than direction to test for connection. Though I'm not 100% sure on how their test for connections is working with the opposites array as it seems to do an insert into a table on rtoate. I think where I'm actually struggling is testing for connections to straight pieces as depending on how it's rotated another piece could connect to either the north or south but both at the same angle. i.e for a straight piece north is south and vice-versa. I wonder if that's why the lua example seems to use frames... \$\endgroup\$
    – TommyBs
    Nov 18, 2016 at 19:07

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .