Jump to content

  • Log In with Google      Sign In   
  • Create Account

Anastas

Member Since 30 Sep 2012
Offline Last Active Mar 06 2014 03:32 PM

#5124905 Tiling a Square Room - Algorithm

Posted by Anastas on 19 January 2014 - 03:16 PM

A 2x2 room is easily filled as, once the empty square is allocated, the mere remainder of the room makes up a single tile. As you can see from this picture, an empty square can also fit into any 4x4 pattern and it is that top-leftmost 4x4 pattern (herein referred to as the TL pattern) that is key for filling any size room.

 

In this example, the empty square has a coordinate of (2,5) in an 8x8 room. Once the first 4x4 pattern was found, the TL pattern from the previous image was wrapped around it and the pink tile filled in what was left. Another way of looking at the process (I'm unsure as to which is more efficient for an algorithm) is the pink tile being placed on the corner of the 4x4 pattern (this corner is also the center of the room; in larger rooms this corner is at the center of a subsection of the room), followed by the TL pattern wrapping around the pink tile.

 

 

The following process illustrates how to fill a 32x32 room with an empty tile coordinate of (2,19):

 

Divide the room into fourths and find which fourth the empty square occupies...

 

Divide that fourth into fourths and find which of those fourths (a sixteenth of the whole room) the empty square occupies...

 

Repeat that process, finding the empty square's position in a fourth of that sixteenth (a sixty-fourth of the whole room)...

 

Finally, find the empty square in a fourth of the sixty-fourth (a two hundred fifty-sixth of the whole room).

 

The reasoning behind finding the empty square's position relative to fourths is that the room is filled via an inverse process. You might find it more streamlined to simply find the empty square in a two hundred fifty-sixth from the start, but the room is still filled by fourths:

 

You take the empty square and generate a 4x4 pattern around it. This can be done similar to the 8x8 example above. The remainder of the two hundred fifty-sixth that the empty square occupies becomes a tile, then you wrap a 2x2 pattern around that with empty spaces becoming a tile (or have a tile attach itself to the corner of the two hundred fifty-sixth [which corner is determined by being in the center of a sixty-fourth] with other tiles generating around that tile).

 

From there, you repeat whichever process you use to generate an 8x8 square, followed by a 16x16 square, until you fill the whole 32x32 room.

 

This process can be used to fill any sized room presented in your problem, but unfortunately I am not so mathematically minded as to translate this process into an algorithm.

 

 

 

 

(P.S. All of the images in this post were created using MS Paint, so you can take your Photoshop and shove it. tongue.png)




#5014060 Turn based strategies without...

Posted by Anastas on 24 December 2012 - 07:02 PM

I can't think of any existing examples, but I can think of a few ways to do this.

Something that immediately came to my mind was how in The Last Story, you see all your opponents before you begin fighting, giving you time to plan out your attack. However, it doesn't quite fit the criteria as it's an action game, not turn-based. But a similar design could be implemented into turn-based combat. I think the main key to get rid of unit placing is to focus the action, to strategize the actions of a party instead of troops.

You could take the standard format of turn-based RPG and do away with the aspect of grinding so that the player must adapt their strategy instead of leveling up to a point where they can just bash their opponents into submission. Instead of each character and enemy getting their own turn, they could each act as groups, allowing you to control the order in which your players attack.

Final Fantasy X let you see how your moves would affect who's turn it is in battle. Something like that in a game more designed around strategy would be pretty sweet.

 

 

Perhaps it would be useful to more clearly define strategy, given you're using it in a broader sense than usual, as I think combat -- even if in an abstract form like Chess or Checkers -- is probably the most natural way of expressing it.

 

That's still moving units across a map to kill other units. tongue.png




PARTNERS