next »

[Crimsontide]

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.

[Dacke]

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.

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

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

[nikki]

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

The next step was to reduce the number of terrain transition variations from 256. This number can be cut drastically by separating the "edge" transitions and the "corner" transitions. As it was pointed out above, a single terrain cell has 8 points of transition: one for each side and one for each corner. Thus, there are only 16 possible edge transitions, and 16 possible corner transitions. By using combinations of edge and corner transitions you can create all of the necessary 256 variations with only 32 total tiles. This is a huge reduction in graphics required.

The template we used followed a binary format. For the edges, west was considered "bit 0", north was "bit 1", and east and south were "bit 2" and "bit 3", respectively. Similarly for the corners, the northwest corner was "bit 0", the northeast corner "bit 1", and so on. How we arranged the actual terrain transition graphics is demonstrated in Figure 3. If you think of the covered edges as 1 and the non-covered edges as 0, you can see that the columns proceed in normal binary manner: 0000, 0001, 0010, 0011, 0100, and so on.

With this method drawing the map is now a 2-step process. For each map cell, the base terrain must be drawn, and then any transitions that overlay it in reverse order of precedence (lowest precedence drawn first). However, the reduction in graphics required more than makes up for the additional work. Also, since the transition graphics are mostly transparent, the actual "work" involved is less than it might seem.

Using the precedence established earlier, and the bit assignments for the edges and corners, calculating which transitions you need in a particular map cell is relatively straightforward. Essentially, for each map cell, you check all adjacency possibilities for terrain types that overlap the terrain of the cell. The transition information for a single terrain type need only use 8-bits of data (4 bits for the edges and 4 bits for the corners) which fits conveniently into a single byte. Thus, the total terrain transition information for Artifact's 9 terrain types requires only 9 bytes per map cell.

 

[Sqorgar]

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.

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:

The next step was to reduce the number of terrain transition variations from 256. This number can be cut drastically by separating the "edge" transitions and the "corner" transitions. As it was pointed out above, a single terrain cell has 8 points of transition: one for each side and one for each corner. Thus, there are only 16 possible edge transitions, and 16 possible corner transitions. By using combinations of edge and corner transitions you can create all of the necessary 256 variations with only 32 total tiles. This is a huge reduction in graphics required.

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 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. 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.

[darkhog]

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.

[nikki]

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).

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 ?

[Sqorgar]

*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)

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.

*and thus you don't need the 15 edge AND corner tiles.

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".

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

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.

[nikki]

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. 

[doihaveto]

I advocate a rule system 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).

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!)

[Sqorgar]

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...

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.

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

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

[guy walker]

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.



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



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
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
along with a [Stage] where you can just play around with different Wang tilesets.
http://www.cr31.co.uk/stagecast/wang/stage.html
Hope this helps, Guy

[BorisTheBrave]

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.

[Sqorgar]

I think you are better off using corner tiles to create terrains. And not edge tiles, as depicted in some replies (#2 and #42).

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.

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.

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.
 

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...

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!

[Sqorgar]

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.

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.



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.




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.

[BorisTheBrave]

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 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.

you've removed the possibility of a few tiles from appearing completely (for instance, you won't have any tiles with adjacent corners)

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.

[Sqorgar]

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.

[Crimsontide]

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.

[Sqorgar]

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.

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.

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.

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.

[BorisTheBrave]

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.

[guy walker]

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

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…

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!

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