TIGSource Forums

Hello,

i am trying to implement a tile transition.
i've found this handy article http://www.gamedev.net/reference/articles/article934.asp (http://www.gamedev.net/reference/articles/article934.asp)

the thing i don't fully grasp is the bitwise technique they use.
i believe checking each cell in a complicated if, elseif way for 32 different posibilities is not exactly the way to go, and thats why i suspect the usage of bitwise things, but i don't get it, 

Has anybody here had some experience in a technique like this ?, and could you explain the neighbour checking ?

Personally I'd do it the if/else way and just pre-cache the result.

Accounting for every possible transition between tiles is going to enter massive if/else territory whether you like it or not. Perhaps the better solution would be to reduce the number of possible transitions.

edit An expanded version of this post is available at my site here (http://www.saltgames.com/?p=184). /edit

The bitwise technique basically does the same as a huge if/else statement, but saves on typing.

Much easier to first think of it first for a map with just two types of terrain - let's say rock and open air.

A simple map might look like this, with the filled tiles being where there's rock:

(http://www.saltgames.com/wp-content/uploads/2009/12/filledGrid.png)

The key to the bitwise method is to assign a value to each tile depending on its neighbours.  For this example let's use the following values:

(http://www.saltgames.com/wp-content/uploads/2009/12/edge-values.png)

We visit each tile that is meant to be filled with rock, and examine its immediate neighbours to come up with a number for that tile.  If the tile directly above this one is also filled then the number is 1.  If the tile directly above AND the tile directly below is filled, then the number is 1 + 4 = 5.

Here's that tile map filled out with the correct numbers.

(http://www.saltgames.com/wp-content/uploads/2009/12/numberedGrid.png)

The clever bit is we can now directly convert those numbers into graphical tiles, so skipping having to write a huge if/else statement.  Here is a tileset, laid out in the order matching the valuing system we picked:

(http://www.saltgames.com/wp-content/uploads/2009/12/tileset.png)

See how each tile graphic matches what would be expected of its corresponding number?

Now our game can just look at the number calculated for each filled tile, and pick out the correct tile to place there:

(http://www.saltgames.com/wp-content/uploads/2009/12/floatingIsland.png)

It would be the same principle even if you want to consider diagonal neighbours, or more varied types of terrain.  You'll just end up with a larger range of numbers.

The reason it's referred to as bitwise is because the values we're assigning to neighbouring tiles follows the same 2^n pattern as binary numbers.

I nominate this to be the most helpful thread response ever.

Yeah, this is pretty damn handy.  Bookmarked!  :)

thank you for the wisdom and clarity of thought ;D  very cool!

While you were making that GREAT little tutorial, i went deep in the google power and learned by myself,
when i figured the binary business and the careful laying out of your tilemap out.

it is a brilliant technique , instead of writing endless if elseif (and nested aswell) mumbo jumbo , i only need 4 or 8 if statements , you add the outcomes and voila your tilenumber !

It felt so great i started drinking beer, and now hav written an scrambled post  :beer:

Ok rolled this into flixel.  I also built an alternate 12-tile variant that doesn't handle 1-tile wide or 1-tile tall solid areas, but DOES do interior corners.  Is handy if you're doing zelda or RL instead of cavestory or mario :)

The greatest most effective short tile tutorial i have ever read... :o :beg:
It solve one of my concern with 3D tile and i also figured that i could use bit on diagonal to distinguish between a turn and a solid corner... :noir:

In fact i works with any isotropic shape tile system, as long as yout correctly tag bitwise neighbor cell  :wizard:

Officially awesome

Good stuff! Also, Gyorgy Straub used this for some tiles for Assemblee - here (http://forums.tigsource.com/index.php?topic=9200.msg286272#msg286272)

Oh, I never thought of doing it that way before.  Nice : D

That is an amazing technique, thanks a ton.

I used this same technique in Sim Cavern and it works really well. I ended up with a 4bit, 16 tile internal wall system that was very easy to work with, as well as nice and dynamic.

I'm working on a corner based 4bit x 4 system. It would require 64 x 1/4 size tiles to draw though, which may be a bit much. It would mesh a bit better though.

This is ace, thank you Salt :)

Wow, this is so simple. I got it working in Game Maker in about 2 minutes. Thanks, Salt  :beer:

ooo this is a nice explanation, bookmarking!

Bit of an old topic, but this deserves some attention :D
I was looking at this thinking this is one of those things that sound like it should work easily, but require alot of tweaking. But I worked on this for about 2 hours yesterday and it works perfectly.

However, there seem to be some situations where you can't solely depend on this technique:
(http://img855.imageshack.us/img855/6596/exampletransitions.png)

Both are grass transitions, but they need to respond differently according to their surrounding tiles. There is no way to work around this then by using if statements right?

I could sort of see this working with different values for the surrounding tiles, water having higher numbers values than sand for example. But I am nowhere near genious enough to come up with an elegant solution for that  :droop:

Well, omgnoseat, this can easily be expanded to supporting that.

Just have the standard 1 2 4 8 for the four water tiles around the grass tile, but then carry on the progression for the four sand tiles, so they would be 16 32 64 128. This should still generate a completely unique number, this time between 0 and 240, and so you should be able to support 8 different textures in a standard 32 bit integer,  and there are probably other workarounds too.

This article (http://www.squidi.net/mapmaker/musings/m091016.php) does a good job at looking at all of the different types of connections that you would want from a binary tilemap.

To get perfect inner and outer corners, you need 47 tiles (unless you don't care about inner tile [15 in Sam's example]).

Thanks for the replies guys, was exactly what I was looking for!


I'm currently looking into "the blob" method which is mentioned in the article, but bitwise operations are not mentioned :(
Which values would the 4 corner tiles need to implement this method?

? | 1 | ?
8 | # | 2
? | 4 | ?

Well, you would do something like:

1 | 2 | 4
8 | # | 16
32| 64| 128


Now, if you think about this, this means that you should need 256 different tiles, but luckily as shown in the article, you only need 47.  The tricky part comes from figuring out where the overlap is.  If anyone is interested, I can supply AS3 code to go from the tilesum (as I refer to the sum of all of the bitmasks) to the tile index (assuming that all the tiles are in one row, going from left-to-right, top-to-bottom as seen in the tilemap from the article).

But this would leave huge gaps in your tilesheet right? Since your only using 47 of the 256 spots in your tilesheet. That doesn't really seem like the way to go.

Huh? No.  Not sure what to say other than the fact that you aren't getting it.

Well if you only need 47 tiles but the max value you can get is 256, then that would mean that you have 256 minus 47 free spots that you are not going to use :/
It could be that I'm not understanding correctly though.

No, you just have 47 tiles.  As I said, there are 256 possibilities, but due to the nature of how it actually winds up looking, only 47 of those are unique.  So, you have a tilemap with 47 tiles.  That's it.

Simply add up the values as fallsberg indicated, then look up the tile index in this table:

Thank you boris.

I've been looking into the 47 tiles based completion with a friend. And we understand everything except how Boris came up with the lookup table. So yeah, we're pretty curious how that convertion is handeled :)

Ok, I don't actually remember how I did it either now ;D  Magic, I suppose.

I think basically, for each solid corner, I changed it to empty unless both the adjacent tiles were solid, as that's the only time you get any choice in what the corner is. You're left with 47 combinations, which I renumbered. I might have done it manually though, not sure.

BTW, if you liked that, you might like the tool I released this week for creating blob tilesets.

https://github.com/BorisTheBrave/resynth-tiles/wiki/Tutorial

I don't have transitions in my game
it's kinda weird but I don't care

(http://i.imgur.com/g4D1HDS.png)

And the result is so indie.

Question for Sam: How would you handle "autotiles" broken into 48 possible tiles, as RPG Maker does it:
(http://i.imgur.com/VPLxXf3.png) (http://i.imgur.com/6xBuJBW.png)

Your system wouldn't work for tiles build from sides (to achieve more variety) as it only counts for 16 tile types.

You mean that you have several versions of each type? So 4 different left-tiles, 4 different right-tiles etc.

Just compute the numbers like Sam showed. If you (for example) get number 7, just pick one of the left-tiles at random.

Sam's solution only takes care for 16 tiles, whereas to make perfect autotile you need 47, like it was explained on second page of this thread.

I'm not thrilled about:

because it gives you too much cases to check against. I need something clean.

//edit: TL;DR: Sam's solution will take care of this:

but not this (for example):

Ah, I see what you mean.

You'll get 256 unique numbers, but many of them will map to the same tiles. So you'll just have to figure out which numbers should be remapped.

Then either do some clever bitwise stuff (if you find a pattern), or do something simple like:

You could do it with less.  For 2D tiles you could get away with 'perfect' transitions with 15 tiles.

The technique is similar to the marching squares algorithm (aka, a 2D marching cubes).  Instead of drawing the tiles + the boundaries, draw your tiles at the intersection (ie. offset 1/2 a tile in the x/y direction) of the underlying map.  So if the underlying map is say 32x32, then you would draw 31x31 tiles.

So say were drawing the grass.  Each tile drawn samples/reads from its 4 corners.  Each of the 4 corners is either 'in' (is grass) or 'out' (not grass).  This gives us 16 possible cominations.  All 1's is a solid tile of grass no transitions.  All 0's is an empty tile.  Every other combination is some sort of transition.

All the tiles you would need will look something like:
(http://ej.iop.org/images/1742-5468/2008/12/P12015/Full/0006006.jpg)

So each tile type/layer would only need 15 unique tiles, and you have 'perfect' edges/transitions.  The offset would require a change in drawing logic/code, but player/game logic can still operate as it would (ie. players or enemies or what-have-you do not need to be offset or this applied in any way).

hm... I think I'll just write autotile breaker and just place them by hand.

Crimsontide, you are wrong.  You are only considering corners.  You need to consider corners and edges.


For examples (X is filled, O is empty)

OXO
XXX
OXO

and

XXX
XXX
XXX

Your algorithm will use the same tile for the middle tile, but the 47 tile solution will handle it correctly.

If people really, really, really want my ugly ass mapping of

1 | 2 | 4
8 | . | 16
32|64 |128
to the 47 tiles, I can produce it, but it is ugly as fuck.

No you see Fallsburg you're not considering the offset.  Ok imagine your map looks something like this:

00010
01111
01222
11222

0 is ocean, 1 is sand, 2 is mountain.  In your version 20 tiles are drawn to the screen per terrain type.  In my version only 12 per terrain type.  

Now to keep things clear, lets call the tiles being drawn to screen rects, and the tiles in the underlying map tiles.  As you'll see the two are different, which is what makes the algorithm different.

So we have the map and now were going to draw it to screen.  Ocean is laid down first, no need for transitions or what-have-you since its the background/bottom.  Now we draw the first rect.  The first rect is the intersection of the tiles at coordinates (0,0), (1,0), (0,1), (1,1).  The tile values for this rect are 0, 0, 0, 1.  This corresponds to case 4, so we draw the sand texture at case 4.  The next rect to be drawn to the right then is the rect which intersects tiles (1,0), (2,0), (1,1), (2,1), with values 0, 0, 1, 1.  This would correspond to case 12.  The next tile to the right has coordinates (2,0), (3,0), (2,1), (3,1), with values 0, 1, 1, 1 which is case 14.

The case values for sand then drawn to the screen would be (in hex to keep formatting easy in text):

4CED
6B33
E900

The '4' rect straddles the first 4 map tiles.  The 'C' rect straddles the next 4 map tiles.  The '4' rect and the 'C' rect touch along their left and right edges respectively.  The '6' rect and the '4' rect touch along their bottom and top edges respectively.  Is this starting to make sense or perhaps a visual...

Or maybe consider this random image from google:
(http://origin-ars.els-cdn.com/content/image/1-s2.0-S0098300411002548-gr2.jpg)
I'm not sure why there is an a and b, and ignore the Q's.  But imagine that the tiles in the map are the solid shaded boxes, and the rect being drawn to screen, is the box with a dotted edge.  Each drawn rect intersects 4 map tiles.  Because of this there are no edge cases to consider, only corner cases.  In fact the edge cases aren't even needed because they are already taken care of implicitly.

The only real draw back is that you 'lose' 1/2 a tile on each edge of the entire map, but this is really a negligible drawback.

Ah, sorry misinterpreted the image (and didn't really read the post).

In that case, I guess the biggest problem is that you split up your tiles into quarters making larger patterns (on the scale of a full tile) impossible.  That's a minor "problem", but something to be aware of. Also, it assumes that tiles must be able to be split into quarters, again probably not a major concern, but something to be aware of.

Sort of, no less or more so than any other tiling system.  The underlying map is unchanged.  You still have completely filled tiles (case 15), and completely empty ones (case 0) where the tile isn't cut up in any way.  You can still have larger patterns.

There are some changes in that unique features that require a specific location will have to be either 'cut up' (as you say) or overlaid (IMO the preferable solution), but thats only in the case where a feature has to be at a particular location.  But that applies to any tiling system where features have to be located across grid boundaries.

Really nice solution, Crimsontide. It's nice to have multiple options.

Fallsburg, please post your code! With 47 cases it's bound to become ugly and it's always better if people don't have to reinvent the mapping.


Why? It's not that hard really, do you need help with something specific?

the link in the original post that started this thread (in 2009) has some relevant info.



(http://uploads.gamedev.net/monthly_06_2011/ccs-8549-0-92862100-1307467497.gif)

(http://uploads.gamedev.net/monthly_06_2011/ccs-8549-0-57863900-1307467523.gif)



(http://uploads.gamedev.net/monthly_06_2011/ccs-8549-0-72590800-1307467558_thumb.gif)

(http://uploads.gamedev.net/monthly_06_2011/ccs-8549-0-49235600-1307467558_thumb.gif)

 

I see a lot of programmers spend an inordinate amount of time trying to reduce the number of tiles they have to draw by breaking the problem up into quadrants or drawing multiple tiles on top of each other. The problem with this is that any decent pixel artist will be able to do something with a full tile rather than just bits and pieces.

Also, the effort you apparently save will ultimately keep you from using a broader, more useful autotiling system. For instance, the following bit:


Breaks it down into 32 tiles by breaking the edge and corners into two separate problems. It doesn't include the 15 tiles that include edges AND corners, instead proposing that each tile on the screen be drawn up to four or five times each (which is not always possible when working on slower mobile devices). Then it makes several assumptions, such as transitions exist outside the dominant terrain and that the relevant edge/corner information is contained within each tile, which is wasteful when you consider that you would still need to check neighboring tiles to see what kind of transition you need. Ultimately, this approach solves one specific problem and spends a lot of time and memory on it, rather than using a more general approach which could have benefits outside of simple transition tiles.

I advocate a rule system (http://www.squidi.net/three/entry.php?id=166) which can produce a whole host of different effects, like drop shadows, randomized terrain, muti-terrain transitions, tiles which only have a few rules, poser tile types, and even represents a superset of the problem that allows you to use quads if you still want to (but only in the few situations where they are appropriate).

I've built this rule system several times, including a JavaScript version you can play with here (http://www.squidi.net/threep/p166/). The main problem with the rule system is that it is somewhat slow over a large area - but you only need to do it once at the beginning and save the results, and if any tiles change, you only need to recheck the rules for that tile and the surrounding eight tiles.

Well, creators of RPG Maker somehow achieved this and I'd like to have it as well, but as I said I can write program to breakup autotile into individual tiles and then place them manually in map editor.

Would save me programming headache, though I'd still would want to have other viable solution.

don't over react:
 *you don't draw each tile four to five times. you draw a base, depending on which neighbours are where you possibly draw one edge tile and/or one corner tile. (max 3)
 *and thus you don't need the 15 edge AND corner tiles.

your rule system is nice, it's also the same thing as the stuff on the first page here.
Or how is it different ?

Assuming a single transition per tile. But assume you have a subordinate tile surrounded by three or four dominant terrain types, meaning that there would be four transitions imposed on top of it. Granted, this is a worse case scenario. You probably aren't going to be checkerboarding your terrain, but with even just three different terrain types that occur closely together, you can end up with something like:

. = sand
" = grass
# = rock

"#"
.."
#."

This would cause the center sand tile to be drawn multiple times.

1. Sand terrain
2. Grass edge on right side.
3. Grass corner at top left.
4. Rock edge at top.
5. Rock corner at bottom left.

A decent pixel artist could do something interesting with an edge and corner tile. For instance, a sand tile with a grass edge and corner could have extra tuffs of grass in the center to indicate that the grass is growing together across the sand.

Those extra 15 tiles don't amount to much if you aren't going to do anything special with them though, so really, this is more a case of "could of" rather than "should of".

It's a superset of the problem. Rather than solving a specific issue, it solves a bunch of issues that most people haven't even considered. For instance, storing the view tile data as bits is really just an unneeded shortcut to keeping a completely separate view tile map - you are still checking your rules and superficially keeping a different view for your model (the ruleset would be the controller in this MVC example), but you are artificially limiting yourself in what you do. What if you have terrain that only requires 4 tiles? Or requires 83 tiles? Go the full MVC.

oh yeah forgot about that, when you have tiles with many different terrain neighbours you could end up drawing more then 3 tiles (as corners and edges)

my bad. 

Yeah, a rule system would definitely be more generally useful - and let you customize the lookup rules in a variety of ways.

People still have to figure out what the right rules are, though. What was interesting about the OP's lookup-based system, was that his system already provided the implicit rules for people (only these patterns matter, and not others), and an implementation that was optimized specifically for them. That's really useful info for people just learning about something for the first time. Still, for my own projects, I'd probably err on the side of greater generality...

(By the way, you've got some cool proc gen articles on your site!)

I think it's probably important to point out what's really going on with the bitwise system - you are still applying a ruleset (check like tiles in adjacent squares), then saving the result in a separate view-map (in this case, integrated into the model-map, which I think is a mistake).

I think that taking a shallow understanding of the process, limits its usefulness and quality, and causes programmers to believe that it is a superior approach to break the problem down into quads (which I also think is a mistake). It's ultimately a procedural generation problem first, a pixel art problem second, and in a very distant third, a programming problem.

Thank you. It's a sort of a hobby of mine.

Wang Tiles: Edge and Corner

I think you are better off using corner tiles to create terrains. And not edge tiles, as depicted in some replies (#2 and #42).
Matching tiles by their edges tends to create pathways. This 2-edge tile set requires 16 tiles and produces a typical 'path' layout.

(http://www.cr31.co.uk/stagecast/art/forums/tig2e.png)

Matching tiles by their corners tends to create patches of terrain. This 2-corner tileset again requires 16 tiles and produces a 'terrain' layout.

(http://www.cr31.co.uk/stagecast/art/forums/tig2c.png)

For 3 different types of edge or corner, you'll need 81 tiles (3^4) with weights of 3, 9, 27 and 54.

I am not sure if dividing a tile into edges and corners has much advantage. It creates a large tileset of upto 256 tiles. The programming is easy but making all the tile artwork is tedious.
Also, you can convert a corner tileset into an edge tileset as shown here:
http://www.cr31.co.uk/stagecast/wang/puzzle.html (http://www.cr31.co.uk/stagecast/wang/puzzle.html)
so in theory you can reduce complex 'combo' edge and corner tiles to just edge tiles.

I am looking into it though as it may generate good dungeons with maze-like corridors made from edge tiles and larger open room spaces made from corner tiles. But I am hoping to use 2 separate tilesets, one edge and one corner, or somehow cheat and overlay corner tile rooms on edge tile corridors...

I've written a web page section on [Wang] tiles,
http://www.cr31.co.uk/stagecast/wang/intro.html (http://www.cr31.co.uk/stagecast/wang/intro.html)
along with a [Stage] where you can just play around with different Wang tilesets.
http://www.cr31.co.uk/stagecast/wang/stage.html (http://www.cr31.co.uk/stagecast/wang/stage.html)
Hope this helps, Guy

Ah dang, I was going to write on Wang tiles at some point, but now you've just done a better job.

Anyway, I've written up different ways of doing transitions, somewhat inspired by Squidi's (Sqorgar's?) article. I cover some possibilities not already mentioned here.

http://personal.boristhebrave.com/tutorials/tileset-roundup

My conclusion is that different tilesets will be useful for different circumstances. But you don't need 256 tiles to do do things based on 8 neighbours - in my most minimal example, only 13 tiles are needed.

Ultimately, some approaches work better for one problem and some work better for another. There's not some silver bullet approach that works in every case to produce the ultimate quality.

That's why I advocate a more abstract ruleset approach, so you can use any and every approach, even on the same map. Use corners for grassy terrain, edges for fences, and other rules for other types of terrain.


You only need 47 tiles for a full corner/edge pattern in practice (for internally connecting blob patterns). That is, for a pattern which only concerns itself with itself and not-itself, any place where you match at just a corner and not an edge is considered two separate blobs, and those cases can be ignored.

47 tiles is still a worst case scenario for a binary pattern. You can get by with much simpler patterns (like a fence, which requires only 16 tiles). In many cases, you'll have patterns which may only need a single tile with a few rules for exceptions. For instance, I have a floor pattern which is not responsible for edges (the ceilings/walls will provide the edge patterns), but does provide drop shadows for walls/ceilings. There's 4 floor tiles and 6 floor rules total. And it looks snazzy.
 


Generating the dungeons themselves is a different discussion altogether, but I think you may be a barking up the wrong tree here. The goal of generating a dungeon is to present a specific experience, and relying on pure randomly occurring patterns would make it difficult, if not outright impossible, to control the generation in meaningful ways. But I'd still be interested to see what you come up with!

The problem I have with your mini-blob is that you are essentially breaking the problem of each tile into quads, which leaves you with... another blob pattern. You haven't changed the problem at all. It's just by ensuring that tiles occur in a specific grouping, you've removed the possibility of a few tiles from appearing completely (for instance, you won't have any tiles with adjacent corners). So the problem is just as complex, maybe more so, and less broad, and for the sake of saving yourself from having to draw two dozen tiles.

(http://www.lemon64.com/games/screenshots/full/l/laser_squad_05.gif)

This is a screenshot from the old game Laser Squad. The walls there use a fence pattern that does not strictly fall into something that is easily broken into quads. I mean, you CAN break it into quads - since the tiles are interconnected, it stands to reason that they would be interconnected at the same points - but it would not be so pretty when your quad only has a third of a piece of a wall and a bit of roof.


(http://venturebeat.files.wordpress.com/2011/02/laegg.gif)

Here's Link's Awakening. The top tiles of the mountain don't follow the same pattern as the lower tiles. There's a perspective thing going on that makes the frame appear higher than the rocks. If you break this problem into quads, you'd need to, at the very least, create a unique case out of the upper mountain tiles. However, if you don't break it into quads, it's not a unique case.

It looks good breaking a tile into quads when it is a pattern that naturally appears in quarters. When it doesn't naturally break down, you end up with turning something obvious into something obtuse. Not worth the effort.

Yes absolutely, I think it clear you lose some flexibility with the sub-blob pattern. And of course, you cannot draw anything more than the blob pattern, which is why I named one after the other.

But, it is less than half the amount of tiles to draw, at half size no less, that is going to be a big win for some artists. And the code is substantially simpler than the blob pattern, too. Perhaps I could have been more clear on the trade-off.

You can do reasonably convincing perspective (http://vxresource.files.wordpress.com/2010/03/tilea2.png) and fences with the sub-blob, though I agree the sample you've provided is not do-able - you can only have perspective of up to half a full tile, and only have corner curves of half a tile in radius.

I think one of us has misunderstood. Every tile from the blob pattern can be made out from the sub-blob pattern. You cannot customize them to quite the same extent, but they can be made.

I meant that the sub-blob is still a blob pattern. You haven't changed the nature of the solution. What you've essentially done is increase the complexity of the pattern at the cost of having fewer tiles to draw.

For instance, you have four quads:

AB
CD

To fill the entire thing with a blob tile, you can consider ABCD to be blob tiles themselves. However, because they are taken as a square, we can assume that certain patterns will not be needed. For instance, A will only ever have the top left corner cut out of it - the other three corners will never be cut out because we have ensured that AB and AC will only ever connect as edges (and A will only connect to the north and west as edges - the only corner relevant in A is the top left, all others can be ignored). Therefore, you can throw out any tile pattern that has more than 1 corner cut out of it. That's where you are saving tiles from.

But what is ultimately happening is that you are taking one very broad solution with zero special cases and making a very complicated solution with a bunch of special cases. As a general rule, this tends to be harder to use, harder to debug, and harder to expand upon. To do what? Programming something that will be done a thousand times a frame to save you a few seconds doing it manually in Photoshop once?

Take the broad, simple solution over the specific, clever solution every time. You will thank me later.

I'm sorry but if given the chance to trade off my time for computational time, I'll almost always let the computer do it for me.  With even low end modern hardware I can easily pump out hundreds of thousands to millions of 'tiles' per frame(depends on size, hardware constraints, resolution, ect...).  Drawing a single tile 20 or 30 tiles is nothing.

The rule-set solution has advantages, but it also has disadvantages.  Its not a 'one size fits all' solution, there rarely is ever one.  If the map doesn't change a lot, and the rules are simple, then its a nice solution.  But a complex rule-set can be quite difficult to maintain, and in some situations (real-time simulations on the map) having a 'pre-pass' required to render is not an option.  For example if I wanted to simulate physics on the fly on the video card, distilling an arbitrary rule-set into a shader can be a difficult task.

Then create a program that will make the tiles for you. Honestly, how long does it take to cut and paste? SECONDS? If you use Photoshop, you can create macros that will do it for you.

How much "me time" are you saving after you factor in programming and debugging time? Premature optimization is the root of all evil.


After the first pass creating the view map, you don't need to do a full pass again. When you change a single tile, you just need to run it and the surrounding eight tiles through the ruleset again. With even low end modern hardware I can easily pump out hundreds of thousands to millions of ruleset checks per frame(depends on map size, ruleset size, ruleset implementation, etc...). Updating a handful of tiles a frame is nothing.

Even in a worst case scenario where you do need to do a full pass on the entire map every frame, the ruleset process is independent of anything else going on in the game. You can push the process off onto another processor thread, or you can break the procedure into smaller updates that can be done over a number of frames. The ruleset is never going to be your worst bottleneck.

But what it can do is amazing. It does everything that every post in this thread can do, and it can do more. It's simple and obvious, a broad solution that works in many cases to produce quality results with relatively little effort beyond defining the rules. You can take an array of program-readable integers and turn it into a beautiful map that most players wouldn't know wasn't crafted by hand. It's not about saving time. It's about creating possibilities.

Squogar, I think you have become a bit blob-centric.

It is true that you could consider the subtiles to be selected parts of a blob pattern made at half size. But that is your supposition, not a fundamental property of the pattern. I could also say that the blob pattern itself is just selected parts of the 256-tile pattern, and therefore is more of special case. That line of reasoning could go on forever. You can actually draw some things with the 256-tile solution that cannot be done with the blob pattern, but none-the-less most people would prefer the trade off the blob pattern offers, as the extra flexibility (which is small) is hardly worth the enormous extra effort.

The sub-blob pattern exists on its own, it requires 20 tiles, all of which have substantially less complexity than most of the blob pattern tiles.  It can even be considered *less* special casey in the sense it is much shorter to describe in code.

---

Also, one thing I think you may be missing, is that I'm not necessarily talking about tiles from a engine point of view. It probably makes sense to use the blob pattern in your engine even if you designed it with sub-blob, for efficiency, and because as you say, it is kinda a superset of several other patterns you may have drawn. But for artists, it literally will not have occurred to them they could save a lot of work, unless one points out the possibility.

Thanks for the link explaining your 'blob' terrain tiles. Never really taken the time to fully understand it before.
It may be a good technique to help create a dungeon 'rooms over corridors' layout. I like 47 tiles. 16 can be too few and above 60 or so is too many to easily produce.

Anyhow, I've decided to add a 47 blob tileset to the javascript stage, so I can play around and see how it works. I've made a test tileset…

(http://www.cr31.co.uk/stagecast/art/forums/isle.png)


hmmmm I have to agree. I did get a dungeon layout working once, but the result was just a little boring. Too predictable and a bit odd. It might need a lot more effort / skill to get things to work properly. The best option is probably to link together prefab rooms. However I persevere as:
1/ it's kinda fun
2/ the tiled layouts are pretty
3/ a breakthrough making all worthwhile might just happen  ;D

I don't think it is impossible to create something through randomly occurring patterns. I think the trick is to identify the patterns after the fact. A sort of "oh, I have pattern X followed by pattern Y, and these are the seven different things I can do with that". If you identify enough patterns and do something smart with them, you can create something unpredictable and surprising. Something you might consider is to use agents to go in and modify the level towards specific goals, using the initial patterns as a sort of guideline rather than the end result itself.

I've, personally, never approached it that way because I'm a top down sort of guy. I want to be able to say the player is going to find the key in the chapel after defeating a mini-boss, which unlocks the door to the catacombs where he fights the undead zombie king. I've spent considerable brain energy on solving that particular problem (http://www.squidi.net/three/c_procedural.php) without really considering any alternatives.

The 256-tile solution would factor in edges that don't overlap corners, which won't produce quality output. In practice, I would be surprised if anyone could create an attractive tileset in that format.

But blah blah blah. The point is, you are doing the following:

- Using a ruleset to determine which blob tile goes into a particular cell.

- Using a different ruleset to determine which four sub-blob tiles go into that cell based on the previously determined tile.

That's a two step process and the second step feels like a step too many. At this point, it's not about solving the terrain issue and more about proselytizing. People are free to do it however they'd like. It's just that, to me, it feels like a premature optimization.

The blob is a specific binary pattern that is not nearly as common as you would initially think. In most cases, you'll have only one or two blobs per tileset - maybe zero. I have this zombie town tileset I made that doesn't have any blobs at all, and it has about 190 tiles in it. There's probably even more patterns that I haven't bothered to formalize yet (like a solid blob with no holes, non-binary patterns, or even patterns which exist on top of other ones).

What I'm saying is, don't count your chickens before they hatch. Don't waste time solving for problems you might not even have. Save time after you've wasted it, because then you know exactly how much time you will save - and how much time you're going to waste saving it.

Take a look at my provided code for the sub-blob. I am explicitly *not* doing that - I go straight from adjacent tiles to choice of subtiles, very neatly. I just explained the sub-blob in terms of the blob for clarity. An alternate explanation could avoid any mention of the blob.



Yes, there's a definitely limit to the utility of patterns. I know you've recommended rulesets over patterns, but I have some thoughts to pitch in on that too. But it'll wait for a later article.

---

On non-binary patterns (by which I assume you mean when you want to blend more than 2 textures or colors together), I have the following observation.

You can define the dimension of a pattern to be the exponential power of tiles needed to use n-colors. This is in analogy to fractal dimension (http://en.wikipedia.org/wiki/Fractal_dimension). This is one measure of how complicated the pattern is.

For example, marching squares requires 4^n tiles, so it's dimension is 4. This can been seen as there are n choices for each of the 4 corners. The sub-blob needs less than 4*(n-1)*3^n tiles, so it probably also has dimension 4. The blob, I *think*, has dimension 8, though like the sub blob, there is some choice in exactly how to generalize to n colors.

The lowest dimension pattern I can think of is 3. I'll go over what that is, later.

Success !!

Managed to get the 47 tileset working with the tiles I made yesterday
(updated the image to show tile index numbers / weighting  and added grass)

You can play around with it at the usual [Stage]
http://www.cr31.co.uk/stagecast/wang/stage.html (http://www.cr31.co.uk/stagecast/wang/stage.html)
Also added a balance control to alter landmass. Here's a grab:

(http://www.cr31.co.uk/stagecast/art/forums/islegrab.png)

Boris -the link to your lookup table of size 256 is broken on your site  :(
Would be interested to see exactly which tiles you mapped to the allowed 47. Any alternative lookup table would produce very different layouts. Could be interesting.

Might add a short tutorial later...

Thanks, fixed. I think my table is identical to yours, except I consider tile 0 to have an island in the center, and then have a separate water tile.

I like your stage setup very much. I wouldn't have thought of your grass addition to the blob, which I think illustrates an important point about it's behaviour. I'd love to know how you are randomly picking your tile47 tiles - you've included some combinations (specifically narrow water channels), that never appear when you are considering the tiles as trying to border a spaced defined by whole tiles.

Also like the inclusion of some geomorphic tiles, where all tiles can border any other ones.

Glad you like it :-)

Here is the step by step method. I just kept it as simple and as random as possible.

This diagram may help. It shows a layout of just 12 blue tiles, 4 wide by 3 high (the black outlines). The centre of each tile is a yellow square. Each tile has 4 corners (red circles) and 4 edges (green rectangles).

(http://www.cr31.co.uk/stagecast/art/forums/array.png)

1/ Create an array to hold the random data (white lines). You can see that each cell of the array holds a tile corner, edge or centre. It needs to be 'twice plus 1' the width and height of the tiles. So for 4x3 tiles it is 9x7 cells.

2/ Fill each cell with a random '0' or '1'.

      Note each tile 'covers' 9 cells. We can ignore the central cell. (It will always be drawn as a 'blob' of land). So we need 2^8 which is 256 different tiles. This is too many. But we can reduce it to just 47 different tiles by the following clever method:

      For each tile, if the edge is a '0' then make both the corners, either side of the edge a '0' as well. So…

3/ Step through the array, just visiting the tile centres. You only need to check the top and left edge of each tile. If this is '0' then set both corners either side to '0'.

   // if top = 0:    topLeft = 0, topRight = 0
   // if left = 0:    topLeft = 0, bottomLeft = 0

4/ This leaves right column and bottom row of the array unchecked. You can correct this, or simply set all array border cells to '0', which creates an island-in-the-ocean design.
   
      Finally, calculate the index for each tile. The tile47 image shows the weightings used, which by convention 'scan' from topLeft to bottomRight.

(http://www.cr31.co.uk/stagecast/art/forums/isle.png)
 
5/ Step through the array again, just visiting the tile centres. Add up the corner and edge cells with the following weightings:

   // index = topLeft + 2*top + 4*topRight + 8*left + 16*right + 32*bottomLeft + 64*bottom + 128*bottomRight

You should end up with an index of one of 48 numbers. This represents the correct tile to be used.



And that's it.

When randomly filling the array, it's best to choose more 1's than 0's, as many 1's are 'lost'. I added a balance control so you can alter the land mass between 50% and 90%. At 100% it's all land and 0% all water.


Boris -it's interesting that you think there are too many 'narrow water channels'. I'm picking the tiles randomly by the above method, so they must just 'naturally' appear between tiles. If you roll your mouse over the [Stage] a red square outlines each tile. Or choose label to show tile index numbers.
I must admit I was expecting more solid areas of unbroken land to form. I thought I could create an alternative lookup table to control this, but it's not possible.

Will now try splitting the edge and corner cells, so each can have a different balance of 0's and 1's. Should be able to reduce the land 'fingers'. Not sure if it will work...

What I meant was that that the way I would have randomly generated it would be to fill each tile face with a random 1 or 0, then mark each vertex as 1 if and only if all 4 surrounding tile faces are 1. and each edge if and only if the 2 surrounding faces are 1. This method never generates narrow water channels, but it is conceptually convenient as you are only coloring faces, vertices and edges are inferred.

Oh I see !!!
A totally different method (well to me anyway). You only add corner or edge land when surrounding (4 or 2) tiles are also land. Might not be 'messy' enough. I'll try it out. Would be good if a second method makes a very different kind of layout.

Meanwhile… I did experiment with adjusting edges and holes, but not good. Became too complex as both interfered with each other. Anyhow, found an easier solution. I noted that there were lots of 1x1 holes forming at tile corners. So I just removed them.

It doesn't affect the code that switches corners to 0, or that code it, so everything works better. I also include a 'spoiler' so 10% are not filled in, just for visual variety.

Finally, I've redrawn the tiles. Fingers of land are now boardwalks. Works for me. Almost rooms and corridors. Here's a pic. Uploaded to cr31 site.

(http://www.cr31.co.uk/stagecast/art/forums/Isle_47.png)

OK - added in your method Boris, (thanks for your explanation)
It produces good interconnected island layouts. Slightly more sparse and a bit different and a bit more unpredictable but 'messy' enough. Also as you say easier to calculate.
Added a checkbox next to the balance control to select this option.
http://www.cr31.co.uk/stagecast/wang/stage.html
Both methods are good, so kinda 2 4 the price of 1 :)

Could you post sample code and image where instead of graphical tiles, tile IDs (numbers) are shown?

I now treat these tiles as Wang tiles, so apply weightings clockwise from the top.
index = top + 2*topRight + 4*right + 8*bottomRight + 16*bottom + 32*bottomLeft + 64*left + 128* topLeft

Recommended as simply multiply the index by 4 (mod 256) to rotate 90 degrees. Useful when exporting from Photoshop. Or when sprites interact with the tiles (x2 for 45 degrees).

(http://www.cr31.co.uk/stagecast/art/forums/tileset47.png)

Each tile has its index below plus any other 90 degree rotations. Each is x4 (mod 256) the one above.

In theory you can convert the 2corner to a 4-edge tileset and add the middle edge to end up with a 5-edge Wang tileset. You can see that there are only 5 different edges (land/sea) in the tile47 tileset.

The step by step method from the post a few days ago is now also on the cr31 website
http://www.cr31.co.uk/stagecast/wang/tileset47.html (http://www.cr31.co.uk/stagecast/wang/tileset47.html)

If you build the array sequentially, you only need deal with tiles above and to the left. So in code:

   // if top = 0:    topLeft = 0, topRight = 0
   // if left = 0:    topLeft = 0, bottomLeft = 0

Hope that helps. Let me know how you get on.