What do you think is the best way to organize a level?

Game Play & Game Design
#1

Hey guys –

I’m curious about all your opinions on the best way to organize a level in a game, and I’m thinking specifically a 2D top-down look akin to SNES RPGs, but this discussion could branch anywhere from there and I’d still be interested. What’s the most efficient way to do this? How should collision be factored? What about “fog” for not being able to look past walls and things? How would you do it, or how did you do it? What do you think is the most widely adopted way of doing this?

I have to this point used a 3D array to handle all static unmoved objects, like walls and buildings. Maybe one or two of them will be moved or deleted at a time, but on the whole the objects in my array do not act, they merely draw and represent the environment and things the player cannot walk through. Every other layer represents a layer the player can “walk” in, that is a layer where walls can block the player and doors can be opened. When a player walks up stairs, the active layer is changed to two layers up. These layers than can be active do not have anything drawn to the screen – they merely have things to decide possible walking locations and whatnot, therefore allowing for invisible walls, or walls that can be walked through, etc. The layers that sandwich them form foreground and background (depending on if they are above or below the active layer), and are drawn, but the player can never interact with them (in terms of collision). So a “passwall” would have a drawn wall, but in the center layer there would be no matching Wall, and therefore it could be walked through even though it may not appear like that should be true.

Agents are all saved in a single ArrayList, which is one thing I think may be poorly designed. This means all characters, monsters, etc., have to be checked for collision with the player at every timestep. I never have too many Agents in the list at once so there is never too much overhead, but I feel there is probably a better way to design this. Because players do not move along a grid and because you can walk through them, I felt it would be inappropriate to save them in the array. Perhaps 5 agents could be overlapping the same position, or be halfway in between what would be two array locations. But is an ArrayList too slow? This means every timestep I’ve already got O(n) going, before animation, having all Agents act(), etc. Slow?

Everything in the ArrayList is told to act every timestep, but the only items in the array drawn are ones on the screen, saving quite a bit of processor. This is obviously a fine idea, but I’m wondering if anyone maybe has a reason not to do this.

As for “fog,” I have straight lines factored in every direction along 36 different slopes (this means one every 10 degrees), then if these lined intersect a wall a black triangle is drawn at that angle along the wall. What results is a very realistic fog in terms of human visibility, but it looks sort of ugly. If I do partially transparent triangles it looks a little better as overlapping areas are darker, but it’s still sort of kinky. How do other people do this?

And that’s my take on it all. How about yours?

#2

First of all, you can replace ArrayList with a Bag from http://www.java-gaming.org/forums/index.php?topic=14938 (or even a plain array) for a small performance boost (the consequence of using Bag is that you can no longer depend upon the order of the elements). Since ArrayList probably isn’t the bottleneck in your program, it won’t make much difference.

With multiple layers, I just use multiple 2D arrays instead of a 3D array. There’s nothing wrong with a 3D array, but I usually draw the different layers in different ways, so the different layers might as well be seperate.

With characters, I stored them in the same layer as walls in the RPG I was working on a little while ago. In retrospect, I think a “sprite-based” approach would have been better so that I could have more variation in character size. I’ve read some books that have introduced me to this approach.

Have a grid (modelled by a 2D array) for the character layer. However, each position in the grid represents multiple tiles. For instance, each position in the character grid could map to 10x10 tiles. The character grid is not a grid of actual characters but a grid of ArrayLists (or Bags) of characters. Each position in the grid stores all the characters in the corresponding 10x10 tiles.

The type of the layer grid would be something like ArrayList[][] except that I don’t think Java allows you to make arrays of classes that use generics for some reason. Potentially, you could just use a 3D array here so long as you made sure there’s always enough space. You could just make each grid position have space for 100 characters, which would make the array take up as much space as a regular 2D array for the layer (plus the added array pointers).

To do collision detection, you need only check the characters within the same grid position. If the character is close to an edge of the grid position, you will have to check in the next grid position over as well. If the grid positions were small enough (i.e. mapping to 3x3 tiles), you could just check for collisions in the current grid position and all adjacent grid positions.

I don’t know anything about the fog.

#3

This is a terrible idea. Firstly it’s none too elegent code-wise, secondly it forces you to define a maximum player/character size, which you can’t change. Or instead you could just use a quadtree, which is well known and has been around for ages, and is quite elegent to implement. The quadtree is basically what you get by generalising the cludgy larger tiles approach, and doesn’t impose a maximum size.

Although personally I just tend to use a few ArrayLists, unless you’re talking millions of colliding objects you really won’t notice the difference. YAGNI.

I usually like to separate maps by function rather than position. So I’ll have a collection of enemies, one of powerups, one of bullets, etc. This tends to be simpler and more maintainable than trying to use a generic “Entity” base class for every object in the game. Static elements (like a tilemap or other level geometry) I also separate into different layers for rendering purposes.

For fog you could adapt my lighting method: http://www.gamedev.net/reference/articles/article2032.asp

#4

Interesting insight, thanks guys. I intended this more as an open discussion and less suggestions on my particular implementation (I’m very happy with it and it works fine, for the most part.) I’ve just realized (as is evident by your two posts) that there are a lot of different ways to deal with this same case and I wanted to have people discuss how they’ve done or how they would.

That being said, I either don’t understand fletcher’s suggestion about how to deal with Entity’s, or I disagree with it. From your suggestion, you say to essentially create a 2D array of ArrayList’s. So if I have a typical one of my larger levels I’ll have a 100x100 array, which means 10,000 ArrayList’s instantiated! Don’t think this creates a massive memory load? Indeed, factoring collision becomes significantly more efficient, but I’m gussing in most games levels tend to have way way more static objects than active ones, and therefore it becomes a lot cheaper to check every single active object against each other O(n^2) than to instantiate a massive amount of Array Lists. Doing this certainly vastly reduces the number of computations for collision, but really everything will stay O(n^2) in the end anyway. Maybe the divisible difference is a factor of 10 or even 100, but the difference in RAM used becomes significantly more than that.

However, you do have an interesting idea to make things faster. Maybe some sort of optimized version of this would be better, in which there are only 25 or so “collision areas” per level, rather than one per block. This means you’re not spending much memory on ArrayLists, and you can still save processor factoring collision. I think it really depends on the number of collided agents versus the number of statics in your level. If you have significantly more active agents, your method might be the way to go.

Orangy, your shadow system looks excellent. It’s basically the same as what I was implementing but significantly more sophisticated. And because I’m already using OpenGL in my game, it could be really useful. If I happen to use it in the end, what are your rules for using it? I will certainly reference you as the originator of the code and link to your site, but do you require anything else?

#5

When you start to take the effects of cache into account, I wouldn’t be surprised if the speed different was negligable for something that heavy on memory.

[quote]However, you do have an interesting idea to make things faster. Maybe some sort of optimized version of this would be better, in which there are only 25 or so “collision areas” per level, rather than one per block. This means you’re not spending much memory on ArrayLists, and you can still save processor factoring collision. I think it really depends on the number of collided agents versus the number of statics in your level. If you have significantly more active agents, your method might be the way to go.
[/quote]
Now you’re reducing the number of ‘collision areas’ in order to balance it, and again you’re heading towards a quadtree. Hell, you could even have a lazily created quad tree and it’d automatically adjust it’s density based on the load you put it under. But again, YAGNI.

[quote]Orangy, your shadow system looks excellent. It’s basically the same as what I was implementing but significantly more sophisticated. And because I’m already using OpenGL in my game, it could be really useful. If I happen to use it in the end, what are your rules for using it? I will certainly reference you as the originator of the code and link to your site, but do you require anything else?
[/quote]
Ideas are free. ;D Fortunately here in Europe we’re still software-patent free.

Somewhere in the far future I plan on writing a new level editor for 2d games, and hope to be able to make it fit for lots of different uses. Personally I see the bigger challenges in the loading and behaviour of the entities themselves, rather than how they’re stored and managed. I tend to go with simple String identifies in the level data, which in turn trigger the creation of the specific subtype needed. Thats great for enemies, powerups, etc., but less good when your data is the same subtype but with varying data (eg. level tiles). I’d be interested to hear how other people handle such a thing.

#6

My idea isn’t unique. I managed to find it mentioned (though not elaborated upon) on the Internet. See the “n-body pruning” part of Optimization at http://en.wikipedia.org/wiki/Collision_detection.

I suspect that is what Orangy Tang is doing with quadtrees, though I only just found out quadtrees were when I looked them a minute ago (though the name makes it fairly obvious). I don’t see how it directly applies to tile-based games unless each point is a node with the movement to an adjacent node being the link between nodes. If that’s the case, it seems to use at least 4 times as much memory than what I mentioned without resolving anything.

It’s more likely that you’re using the quadtree to partition the map somehow. If so, it doesn’t seem like it’s all that different from what I’m doing. The ArrayLists would just be spread out in the quadtree instead of being ArrayLists. I admit that it’s possible that there could be less overhead.

I must not have been clear in what I said.

In the RPG I was working on before, there’s a 2D array for the characters, walls, etc. Things like the ground and the roof are stored seperately (as 2D arrays or otherwise).

Collision detection is simple. Just check the whether there’s an object at the new position (though I actually allow objects to take up more than 1 tile, which complicates things).

My idea would use the same amount of memory plus a small number of pointers.

Let’s say that the map is 100x100. In my old way, there would be 100x100=10000 pointers.

Now let’s look at my idea above. If the blocks were each 10x10 tiles, this would mean that there are 10x10=100 blocks of ArrayLists. Each block would contain up to 10x10=100 characters. This would be 100x100=10000 pointers. It’s the same either way. In the new way it would actually be less because the blocks won’t have to be allocated to the full 100 characters per block because there aren’t going to be characters on every tile.

Assuming that a pointer is 4 bytes, that’s only 40K. You probably have 10000 pointers already for the ground tiles.

The size of the blocks doesn’t affect the amount of memory used significantly. The number of ArrayLists is equal to the number of blocks, but the size of the ArrayLists is inversely proportional to the size of the blocks.

My reason for doing this is to simplify my code for multi-tile characters by making the code more like a sprite-based system. Since I had about 100 characters per map instead of 5 or so like you have, I need to do something other than the O(n^2) check of collisions with all the characters.

I haven’t actually done this yet, but I don’t think it will be a problem when I start on my next RPG project.

#7

If you’ve only just found out about quadtrees, then maybe you shouldn’t be recommending spatial partitioning methods, hmm? Also a quadtree only uses 1/3 more memory than the memory of the lowest level (much like mipmaps). Get your maths right. You’ve also missed the main advantage of the quadtree - that it doesn’t enforce a maximum size on your objects, which I’ll get to in a minute.

[quote]In the RPG I was working on before, there’s a 2D array for the characters, walls, etc. Things like the ground and the roof are stored seperately (as 2D arrays or otherwise).

Collision detection is simple. Just check the whether there’s an object at the new position (though I actually allow objects to take up more than 1 tile, which complicates things).

My reason for doing this is to simplify my code for multi-tile characters by making the code more like a sprite-based system. Since I had about 100 characters per map instead of 5 or so like you have, I need to do something other than the O(n^2) check of collisions with all the characters.
[/quote]
Firstly, 100 characters is nothing, and certainly not a case where you need this kind of optimisation. But we’ll ignore that for now. It’s also not clear whether you’re limiting character movement to the tiles all the time, or whether it’s freeform.

  1. If everything is locked to tiles, and everything is no bigger than a single tile, then by all means use a big array. But practically no game fits this any more.

  2. If objects can move freely, or objects are bigger than one tile then you have the problem where object overlap more than one tile at a time. Sticking with the big 2d array approach, we can either: a) check surrounding tiles within a given radius, or b) insert the objects into multiple tiles.

Option (a) sucks because it means you have to pick a fixed radius to check against. This means you can’t have objects bigger than this radius, otherwise their collision checks can fail.

Option (b) sucks because it’s hard to maintain and verify as objects move. And because objects exist in the array more than once we’ve got to keep a separate list to actually update everything. Thats an additional collection to maintain in sync with everything else. That maintenance is non-trivial too, as you’ve got to do lots of arbitrary removal and add from the tiles. It can work (I’ve done it), but it makes for inelegant and brittle code.

These problems both arise because the objects are no longer completely contained in the partitioning method (the tiles). So we generalise it, and objects which overlap a boundary are placed in a more coarse grid. We keep adding coarser grids until we end up with a root node which contains everything that doesn’t fit in even the coarsest. Store the whole thing in a tree structure and we’ve got a quadtree.

Unlike the regular grid approach:

  • Objects only exist once in the structure.
  • It’s easier to maintain and verify for correctness.
  • The implementation is a dead simple recursive one.
  • We don’t have to start imposing maximum object sizes.
#8

I like it. Quad tree sounds like a good implementation. I’ll have to read more up on it before I understand exactly how it works, but it sounds useful enough that maybe I might want to think about changing my structure to that.

I’ll do some more research.

#9

Since I didn’t know about quadtrees, I couldn’t very well say “I don’t know about quadtrees, so I won’t recommend spatial partitioning methods”, could I?

Athough I don’t recall seeing quadtrees previously, I may have encountered them in some algorithms class when they were telling us about a gazillion different kinds of trees. In any case, this topic is the first I’ve heard of them being useful for something.

I’ve used both options 2a and 2b, and, yes, they both suck.