2

Let’s say I have an object, called “Tile”, which has both a name and a list of directions. We’ll assume that each tile has a 3x3 grid of pixels, which can either be on or off. The middle center pixel (designated with a “N” in the diagram) of the tile turns on when the North direction is “True”. The center left pixel (“W” in the diagram) of the tile turns on when the West direction is “True”. The center right pixel (“E”) of the tile turns on when the East direction is “True”. The bottom center pixel (“S”) of the tile turns on when the South direction is “True”. The middle pixel (“C”) is always on.

Diagram:

 N 
WCE
 S

Each tile can only have one start and end, so there are 6 possible tiles. (Straights East-West and North-South, and all 4 turning pieces which form 90 degree angles)

Here’s an example tile, complete with attributes:

Tile1:
-North: True
-East: False
-South: False
-West: True

Here’s what that tile looks like, if dashes are “off” pixels and percent signs are on pixels:

-%-
%%-
——-

Let’s say I have a list of these tiles, where each tile connects to the one in the list before it, and I am procedurally generating them.

The idea is to be able to generate paths of arbitrary lengths, which do not need to exist inside the bounds of an array.

Of course, I want my map of tiles to be logically sensible, so it cannot have more than 3 lefts or rights in a row. My current “solution” is to have a counter where I subtract one if it turns to the right of the current tile, and add one if it turns to the left. I could then force it to choose a left-turning piece if the counter is at -3, and force it to choose a right turning piece if the counter is at 3. (This algorithm will work with my current generation methods, that is not the problem.)

What is the most efficient way, given the past tiles and their respective directions, to determine whether to increment or decrement the counter?

Sorry if this is a little verbose, I couldn’t think of a better way to phrase my question.

Edit: To clarify, the goal of the algorithm is to determine whether a tile given turns left, right, or straight (which isn’t really a turn, but IDC) based on the previous tiles and return 1, -1, or 0, respectively. That’s it.

  • 1
    If you're trying to avoid that the path crosses itself - e.g. because your algorithm enjoys playing 'Snake' ;-) - then the counter logic will not be enough. Otherwise, the goal of the algorithm is not clear to me. – doubleYou Jan 1 '18 at 23:46
  • I edited my post to clarify what I was asking. I have already implemented another algorithm that works on what I initially needed this for, but I want to know how I would go about doing this if I were going to, uhh, “take this route”. – iPhoenix Jan 1 '18 at 23:51
  • 1
    For those who need help visualizing the task given the verbal description, it is quite similar to an old game in the mid-1990s called Pipe Dream or Pipe Mania. – rwong Jan 2 '18 at 0:09
  • 1
    This sounds like requiring backtracking. Another observation is that, the valid and invalid patterns (short fragments of turning instructions) are rotationally and mirror-image invariant, so that the valid fragments can be memoized, which allows an engine to randomly pull out a fragment from the list, try it, back track if it conflicts with something already on the board. Also sounds something like Markov - given last N moves, suggest a move that is not plainly invalid. Note that "not being plainly invalid" does not guarantee validity on the board. – rwong Jan 2 '18 at 0:14
1

I should reiterate that the counter logic will not be sufficient to keep the path from crossing itself, if that's your goal. If I understand your question correctly, though, you're currently only interested in how to implement the counter.

So we have six distinct types of tiles, which you identified in your question. Determining which of these we are dealing with is relatively simple: we just need to check two pixels, as you call them.

Once we know what kind of tile we're dealing with, the question becomes whether it's a right or a left turn. The two straight types are easy, of course. So let's assume we have the turning tile from your question. Whether this is a left or right turn depends on the direction by which we enter the tile (North or West in this case).

Approach A

Rotate the tile depending on the entry direction, so that you always enter the (rotated) tile from the same direction, e.g. South. Then you simply check the East and West pixels to determine a left or right turn, respectively. If neither are ON, then it's a straight tile.

Approach B

Create a hash table (or similar) for each tile type. Determine in advance, which entry directions lead to left turn (at most 1), right turn (at most 1) and which are invalid (all others). Then it's a simple lookup.

In either case, you'll start with a direction and then sequentially apply the algorithm to all tiles in your path.

  • That’s a very clever method, Thanks! I’d imagine the hash table (Approach B) would require less overhead, but that’s different between languages and the number of times tiles need to be generated, I’d imagine. – iPhoenix Jan 2 '18 at 1:02
  • Less overhead in space or runtime? Honestly, don't even worry about it! Both algorithms are in O(1) space and O(1) time and unless you're dealing with billions and billions of them, performance will not be an issue. – doubleYou Jan 2 '18 at 7:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.