I've been teaching myself Java by creating a 2D (top-down) networked game. I'm finishing up with my server now. Currently the client is just a little program to connect to the server. But it's fast approaching the time to think about how I will store my data.

Currently, I have a simple 2D map array, with the indices corresponding to the X and Y coordinates of a grid. This will work great for my floor tile data, as there will ALWAYS be exactly 1 floor tile every X/Y, forming the grid.

The problem comes with any other objects I wish to add to my map. I don't know how they should be stored.. mostly because I want to allow finite positioning, not just locked to the grid.

I have come up with a couple methods, but nothing that seems .. good.

Method 1)

Store everything along with the map array. This was my initial thought as it is the most obvious.

Map[X][Y] = Object[0..n] , an array of objects. Object[0] would contain data about the floor tile, Object[1..n] contains all other objects (in order).

Problem 1)

This lends itself to wanting to snap objects to the grid. If I have a wall on map[2][2], I would probably put the wall in the exact center of that grid. While this would be wanted for SOME objects, I don't want to be forced to do it for ALL objects.

---- Possible resolution to to problem 1: Thought of this while I was typing. Maybe I could have an OFFSET defined for the object, so it would get the coords of the center of Map[2][2] then add/subtract the offset from the screen's X/Y to get a more finite location. Still doesn't solve problem 2 though..

Problem 2)

This doesn't seem practical for objects that would be moving a lot (Creatures, players, .. moving objects). I would constantly need to remove the object from one Map grid and add it to the next. While I imagine this may actually go fairly quickly, it seems messy and convoluted.

-----------------------------------------------------------------------------------------------

Method 2)

Separate Objects and Grid. So the Map[X][Y] would contain only TILE data.. meaning, information about the grid/floor. All other objects would be stored in separate indices. Ex: mapObjects[0..n]. Each mapObject would contain its own coordinates.

Problem 1)

To draw this, I would need to loop through the mapObjects structure and draw them one by one.. which is fine.. except I can foresee problems with overlapping. Overlapping is fine, but I need to make sure the objects BEHIND are drawn first so that when the objects in front are drawn, they overlap the others. Since the index of mapObjects is simply an incrementing counter, it really doesn't denote any position and obscure drawing will occur.

-----------------------------------------------------------------------------------------------

Method 3)

Combine Method 1 and Method 2.

Basically a less messy version of my problem 1 solution in Method 1. Map[X][Y] = Object[0..n] where Object[0] is the tile data and 1.. n would contain the index into the mapObjects array (where more precise coordinates can be found).

Problem 1)

Still does not address objects that move a lot.

-----------------------------------------------------------------------------------------------

A summary: I can easily create a "lock to grid" based map, which works fine for floor tiles, but when dealing with other objects such as players that can move in more finite increments, I have no idea how they should be stored.

Sorry if I provided too much data (or even too little data for that matter). This topic really isn't Java specific and concepts from all languages could potentially apply.

Thanks for reading,

Chumble

You can forget about methods 1 and 3.

The overlap issue in method 2 wouldn't be an issue if you used the graphics card to draw your stuff, since you could just turn on depth testing which works automatically at the pixel level.

Assuming that's not an option, the next simplest thing to fix method 2 is to sort all your objects to depth order before drawing. Then you can just draw all of them in order, pausing at tile coordinate lines to draw a row of tiles. If you run the sort before drawing every frame, moving objects do not need any special handling. Performance required by this approach shouldn't be a problem at least up to thousands of objects, but likely a lot more than that.

You can forget about methods 1 and 3.

The overlap issue in method 2 wouldn't be an issue if you used the graphics card to draw your stuff, since you could just turn on depth testing which works automatically at the pixel level.

Assuming that's not an option, the next simplest thing to fix method 2 is to sort all your objects to depth order before drawing. Then you can just draw all of them in order, pausing at tile coordinate lines to draw a row of tiles. If you run the sort before drawing every frame, moving objects do not need any special handling. Performance required by this approach shouldn't be a problem at least up to thousands of objects, but likely a lot more than that.

Interesting - I was not expecting that. Any insight as to why method 1 and 3 wouldn't work (you seem pretty adamant)?

You certainly could use methods 1 or 3 to solve the overlap problem, so they would "work", but there's little reason to use them because the alternatives are so much better. Method 1 is especially pointless. Even though method 3 doesn't make sense for just solving the overlap problem, you might still want to use it because it also helps with game logic, such as making it fast to find all objects in the vicinity of a given object.

Depth testing with the graphics card involves zero work on your part and is essentially free performance-wise, so it is faster than any approach based on manually arranging the draw order. If that's not a possibility, then solving the overlap problem is always fundamentally a back-to-front sorting problem. The method I suggested - just sorting everything every frame - is dead simple and works for reasonable amounts of objects. If it's not fast enough, the only option is to optimize the sort.

Method 3 is actually a spatial partitioning scheme, which is one way the sort may be optimized, but it's pretty crude and probably slower than the simple sort for reasonable amounts of objects.

Any serious optimization effort should begin with estimating the quantities involved: how many objects may be on screen at a time, how many of them may overlap, how fast they may move, at what rates they may be created or destroyed.

You can forget about methods 1 and 3.

The overlap issue in method 2 wouldn't be an issue if you used the graphics card to draw your stuff, since you could just turn on depth testing which works automatically at the pixel level.

Assuming that's not an option, the next simplest thing to fix method 2 is to sort all your objects to depth order before drawing. Then you can just draw all of them in order, pausing at tile coordinate lines to draw a row of tiles. If you run the sort before drawing every frame, moving objects do not need any special handling. Performance required by this approach shouldn't be a problem at least up to thousands of objects, but likely a lot more than that.

Interesting - I was not expecting that. Any insight as to why method 1 and 3 wouldn't work (you seem pretty adamant)?

I agree--methods 1 and 3 are not ideal. I think it makes much more sense to store your map and your other game objects in separate structures. Throwing them all in the same data structure is messy. I can't give any other specific reason why you shouldn't do this, except that it's just bad design in general.

Plus if you're doing this in Java, mixing a bunch of different types of objects in this way is going to suck a lot, because you'll either need really clever interface design or a bunch of type checking. It's better that you keep them separate. Keep it simple.

As for the rendering problem, here is the simplest way I can think of to handle it. On each frame:

- render the map

- render the other game objects

This way, you simply draw what is in the background first and work your way to the foreground. If your game objects need additional layering, you can add a z component to their coordinates and sort them somehow so they are drawn in the correct order.

@Yrjö P.:

Thank you for taking the time to reply to this - it has been bugging me for a while. You brought up another interesting point:

You certainly could use methods 1 or 3 to solve the overlap problem, so they would "work", but there's little reason to use them because the alternatives are so much better. Method 1 is especially pointless. Even though method 3 doesn't make sense for just solving the overlap problem, you might still want to use it because it also helps with game logic, such as making it fast to find all objects in the vicinity of a given object.

...

Method 3 is actually a spatial partitioning scheme, which is one way the sort may be optimized, but it's pretty crude and probably slower than the simple sort for reasonable amounts of objects.

This had crossed my mind before although I didn't think of it again until you mentioned it. Method 2 makes it easy to find all objects in a given map. But if I wanted to do something like .. find all objects from 2,2 to 3,3, I would need to do a brute force search through my object structure to find them all (although if they were sorted, I could easily stop once I reached 3,4). Using method 3 helps alleviate this. I agree that it is messy though, but I feel like the solution still *has* to be to index the objects by location.

As for the rendering problem, here is the simplest way I can think of to handle it. On each frame:
- render the map
- render the other game objects

It's funny.. I've been working with a proprietary programming language for medical software for the past 2 years. It was designed around being simple and building interfaces for data entry. Being the person I am, I tweaked it and made a 2D game with it. The problem is, the language is never compiled, only interpreted .. which gives it a TON of overhead. Re-drawing the screen is a great way to make a slow game.

I have a hard time getting into the mindset of "This is a modern language - it was MADE to do this kind of stuff. It can redraw the screen more than once a second and you wont see a problem". So I keep going at this trying to be careful with what I'm doing. I guess it's not really a BAD thing (optimizing the program for performance), but it can lead me to try some strange solutions and make some messy code.

That being said, yes.. I think every time an object changes, I will need to

1) Sort the list of objects

2) Re-draw them

I even cringe writing that because I know in this proprietary language that would not go over well.

This had crossed my mind before although I didn't think of it again until you mentioned it. Method 2 makes it easy to find all objects in a given map. But if I wanted to do something like .. find all objects from 2,2 to 3,3, I would need to do a brute force search through my object structure to find them all (although if they were sorted, I could easily stop once I reached 3,4). Using method 3 helps alleviate this. I agree that it is messy though, but I feel like the solution still *has* to be to index the objects by location.

If I understand your design correctly, your game objects can be positioned anywhere, right? "not just locked to the grid", as you said. So that means that any given point in time, your objects can be literally anywhere. So it doesn't make sense to assign them to grid cells, and then move them to another grid cell when they move far enough.

And yes, using this method, if you wanted to find all objects in a given area by looping over each object and checking for intersection is brute force. It's inefficient. But it's also simple and works just fine for small number of objects. When this becomes a bottleneck, you can replace it with some better based on, for example, a quadtree. For now, just make it simple and make it work. Worry about optimizing later. (See below.)

It's funny.. I've been working with a proprietary programming language for medical software for the past 2 years. It was designed around being simple and building interfaces for data entry. Being the person I am, I tweaked it and made a 2D game with it. The problem is, the language is never compiled, only interpreted .. which gives it a TON of overhead. Re-drawing the screen is a great way to make a slow game.

I have a hard time getting into the mindset of "This is a modern language - it was MADE to do this kind of stuff. It can redraw the screen more than once a second and you wont see a problem". So I keep going at this trying to be careful with what I'm doing. I guess it's not really a BAD thing (optimizing the program for performance), but it can lead me to try some strange solutions and make some messy code.

That being said, yes.. I think every time an object changes, I will need to
1) Sort the list of objects
2) Re-draw them

I even cringe writing that because I know in this proprietary language that would not go over well.

You're using Java on modern hardware right? You can draw 60 frames per second, no problem. So put the limitations of this proprietary language out of your mind, they shouldn't concern you.

I see that you're concerned about performance, and that's okay, but I think you're getting way ahead of yourself. Give this a read: http://c2.com/cgi/wiki?RulesOfOptimization

To summarize the rules of optimization:

1) Don't.

2) Don't yet.

3) Profile before you optimize.

So if optimizing early is making you write bad code, stop doing it! =P

Other advice:

1) First make it work

2) Then make it elegant

3) THEN make it fast

I hope that helps.

It absolutely does, thank you again.

Right now I'm just using a 50x50 map on a single screen, for simplicity's sake. I don't even know what this game will DO, it's really more a practice in Java rather than a game. However, I imagine the map will be bigger than 50x50. I think I will make the appropriate changes to deal with a larger map.

The entire world will be split into Areas.

worldMap[X][Y] = Area

Each area will contain the specific data about each tile in that area.

Area[X][Y] = Tile

I think I will also tie the objects into the area as well... seems to be multiple benefits to this.

1) The player will only be able to see up to 4 areas at a time. No sense looping through every single object in the game if only a few apply.

2) Helps give the GENERAL location of a given object.

I know you said not to worry about optimization, but I think this is a pretty safe and easy thing to implement from the beginning.

I think the last "worry" about my object structure is that I will be putting multiple types in the same array.. including players.

Ex:

Object[0] = Wall at 0,0

Object[1] = Wall at 10,0

Object[2] = Player at 10,10

I'm sure I can handle this from a code perspective, but you mentioned above avoiding this style of data structure. The alternative is to have a unique structure for every single object type. Only things I can think of are Objects (Walls, etc) and Players. Granted, both can fit into the same category to some degree but they will need their own classes.

Having a unique structure for Objects and Players would get messy.. and also destroy the whole overlapping draw system. In order to have them draw correctly, I would need to add a THIRD structure, let's call it Draw. Draw would contain the "draw order" and would simply point to either an Object or a Player.. but now we're really just back to having everything, aren't we? A little different since the Draw would only contain a pointer and not the object itself but .. now we're up to 3 structures instead of 1.

I think that's it.. :)

I think the last "worry" about my object structure is that I will be putting multiple types in the same array.. including players.
Ex:
Object[0] = Wall at 0,0
Object[1] = Wall at 10,0
Object[2] = Player at 10,10

I'm sure I can handle this from a code perspective, but you mentioned above avoiding this style of data structure. The alternative is to have a unique structure for every single object type. Only things I can think of are Objects (Walls, etc) and Players. Granted, both can fit into the same category to some degree but they will need their own classes.

Having a unique structure for Objects and Players would get messy.. and also destroy the whole overlapping draw system. In order to have them draw correctly, I would need to add a THIRD structure, let's call it Draw. Draw would contain the "draw order" and would simply point to either an Object or a Player.. but now we're really just back to having everything, aren't we? A little different since the Draw would only contain a pointer and not the object itself but .. now we're up to 3 structures instead of 1.

I think that's it..

There's another way.

1) Keep distinct types of objects in separate data structures (ArrayLists, for example). The most derived classes of the objects in each don't need to be the same, they just need have a common enough interface to justify putting them in the same array.

2) When it's time to draw, search for the items which you need to draw. Make it a brute-force linear search for now, and optimize it later with a smarter search. Once you have this filtered list (let's say, a total of 1000 objects down to 20), sort them by their Z components and render in the correct order. It could look something like this. My Java is a little rusty, so bear with me:

// This is basically what your classes can look like.
public interface Drawable {
	public void draw();
}

public abstract class Entity implements Drawable {

	public double x, y, z;
    
}

// Note I call it `GameObject`, not Object, so as to not be confused
// with java's built-in Object class.
public class GameObject extends Entity implements Drawable{

	public void draw() {
		// TODO: implement me
	}
}

public class Player extends Entity {

	public void draw() {
		// TODO: implement me
	}
}

Then you need to keep your various game objects somewhere:

// TODO: populate these
List<GameObject> objects = new ArrayList<GameObject>();
List<Player> players = new ArrayList<Player>();

Then you can implement a filter to search for the only the objects in view, given min/max x/y of the current view.

	public List<Entity> static filter(double minX, double maxX, double minY, double maxY, List<Entity>... lists) {
		List<Entity> filtered = new ArrayList<Entity>();
		
		for (List<Entity> list : lists) {
			for (Entity e : list) {
				if (e.x >= minX && e.x <= maxX && e.y >= minY && e.y <= maxY) {
					filtered.add(e);
				}
			}
		}
		return filtered;
	}

You can call it like this:

List<Entity> filteredStuff = filter(0, 480, 0, 640, objects, players);
// Edit -- then you can render:
for (Entity e: filteredStuff) {
  e.draw();
}

Then you can sort them by having entity implement `Comparable`, and using `Collections.sort`. See http://docs.oracle.com/javase/7/docs/api/java/lang/Comparable.html and http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#sort(java.util.List).

Notice that, since your `filter` is a separate, self-contained function/method, you can easily swap it out with alternate implementations, when it comes time to optimize. The inputs and the outputs are the same, but the algorithm can change. Make sense?