Jump to content

  • Log In with Google      Sign In   
  • Create Account


2D Map - Data Structure (Not really Java specific)


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
13 replies to this topic

#1 Chumble   Members   -  Reputation: 142

Like
1Likes
Like

Posted 06 August 2013 - 02:29 PM

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



Sponsor:

#2 makuto   Members   -  Reputation: 833

Like
0Likes
Like

Posted 06 August 2013 - 03:57 PM

I don't know if this helps, but I personally would use method 2. It prevents the map class from having too many purposes/complexity, as well as allows maximum modification in the future. When it comes to overlapping, you can:

 

A) Use some sort of Z ordering (all draw calls are added to a queue and drawn later, in order by Z values)

 

B) Have simple "layers" that physically divide your objects into groups (ex items layer [bottom], players layer [middle], and particles layer [top]). This doesn't prevent interobject communication if you have an interface for it, and might even provide a speed boost by focusing your searches a little more (ex. you can only search for items).

 

C) Use a double-ended list or dequeue so that you can both add things to the bottom to be overlapped at the front of the list, or add things to the top at the back that will overlap everything else. Items would be added to the front while players etc. will be added to the back. If you need more complex layered rendering this might break down though (if you don't just need the binary under/over).


Edited by makuto, 06 August 2013 - 04:15 PM.

Want to get to know my work and I better? See my website: Au 79 Games

I wrote General Tips on the Process of Solo Game Development


#3 Yrjö P.   Crossbones+   -  Reputation: 1412

Like
0Likes
Like

Posted 06 August 2013 - 05:28 PM

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.

Edited by Yrjö P., 06 August 2013 - 05:31 PM.


#4 Chumble   Members   -  Reputation: 142

Like
0Likes
Like

Posted 06 August 2013 - 05:56 PM

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



#5 Yrjö P.   Crossbones+   -  Reputation: 1412

Like
1Likes
Like

Posted 07 August 2013 - 02:12 AM

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.

#6 thok   Members   -  Reputation: 687

Like
0Likes
Like

Posted 07 August 2013 - 05:33 AM

 

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.


Edited by thok, 07 August 2013 - 06:18 AM.


#7 Chumble   Members   -  Reputation: 142

Like
0Likes
Like

Posted 07 August 2013 - 06:55 AM

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



#8 thok   Members   -  Reputation: 687

Like
1Likes
Like

Posted 07 August 2013 - 07:36 AM


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.



#9 Chumble   Members   -  Reputation: 142

Like
0Likes
Like

Posted 07 August 2013 - 08:16 AM

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



#10 thok   Members   -  Reputation: 687

Like
1Likes
Like

Posted 07 August 2013 - 10:18 AM


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?


Edited by thok, 07 August 2013 - 10:23 AM.


#11 Yrjö P.   Crossbones+   -  Reputation: 1412

Like
1Likes
Like

Posted 07 August 2013 - 12:55 PM

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

It doesn't work like that. You can't sort a single array simultaneously by several dimensions of a continuous space. If you use my suggestion and just depth sort the array direction, you only have to brute force search objects with similar depth. Let's say you want to find objects within radius 1.2 from coordinates [5.5 2.1]. This gives us depth limits of 2.1 - 1.2 = 0.9 and 2.1 + 1.2 = 3.3. Then you binary search the array for the indices at 0.9 and 3.3 depth, which is practically free. Finally you brute force search only between those indices. If your map is 50x50 and objects are distributed evenly in the depth direction, only about 5% of them have to be searched in this case. Most of those 5% will be inspected very cheaply because their horizontal distance falls outside the radius.

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.

You haven't even defined a problem, other than the overlap one which was trivially solved by depth sort. It's pointless to talk about acceleration data structures, much less implement bad ones, before you have defined what operations you need them to accelerate. For instance, how many objects will there be at most, and is anything known about how they will be distributed spatially? How many "adjacent objects" queries will be made per tick at most? How many other objects will fall under the average radius of such a query? There is no universal data structure that is good for everything.

If you just want to dig into the technology that exists for this purpose, read about BSP trees, quadtrees or other serious acceleration structures and implement one of them.

#12 Chumble   Members   -  Reputation: 142

Like
0Likes
Like

Posted 07 August 2013 - 02:41 PM


It doesn't work like that. You can't sort a single array simultaneously by several dimensions of a continuous space. If you use my suggestion and just depth sort the array direction, you only have to brute force search objects with similar depth. Let's say you want to find objects within radius 1.2 from coordinates [5.5 2.1]. This gives us depth limits of 2.1 - 1.2 = 0.9 and 2.1 + 1.2 = 3.3. Then you binary search the array for the indices at 0.9 and 3.3 depth, which is practically free. Finally you brute force search only between those indices. If your map is 50x50 and objects are distributed evenly in the depth direction, only about 5% of them have to be searched in this case. Most of those 5% will be inspected very cheaply because their horizontal distance falls outside the radius.

 

Well I wouldn't have done it simultaneously, it would have required multiple loops to take into account both X and Y, but you're right - I really only need to take Y into account. Any overlap that would occur on the X axis would be dealt with when I implement collision... but that's a completely different topic.

 


You haven't even defined a problem, other than the overlap one which was trivially solved by depth sort.

 

The problem described there was referencing objects by location rather than URN. However, it is another example of me underestimating how fast these sorts and searches will actually be. I'll try to let it go and deal with more optimization later.

 

 


For instance, how many objects will there be at most, and is anything known about how they will be distributed spatially? How many "adjacent objects" queries will be made per tick at most? How many other objects will fall under the average radius of such a query?

 

Unfortunately, I don't have answers for these. The game doesn't have a purpose right now. I'm trying to set up a 'skeleton' of a game. If I can get multiple players connected, drawing correctly, and can add/remove objects from the world (and have them be updated/drawn correctly), I will take a step back and determine what direction I want to take this in.

 

 

I get the point you and thok are making - there's no point in worrying about optimization when

1) The function doesn't even exist yet and

2) The implementation isn't even DEFINED yet.

I'll stop worrying about it.

 


There is no universal data structure that is good for everything.

 

No, I'm sure. But changing data structures is not easy. This is one of the reasons I'm trying to be careful about this part in particular. I know I will not get it 100% right the first time, but the closer I can get, the less I will need to convert later. This is another one of the things I get from dealing with my current proprietary language, except one I think is more global.

 

I think all of my questions here have been sufficiently answered, and I want to thank you guys again for taking the time to respond.

 

Thank you. Seriously. You guys rock.



#13 Yrjö P.   Crossbones+   -  Reputation: 1412

Like
0Likes
Like

Posted 08 August 2013 - 09:00 AM

But changing data structures is not easy.

Changing data structures in unoptimized code should be easy. If it's not, that's a warning sign about code quality. Keep things simple, generic and decoupled until you have real reason to do otherwise. (One more reason to not do premature optimization: it makes it harder to later do optimization you actually need.)

#14 Malabyte   Members   -  Reputation: 588

Like
0Likes
Like

Posted 10 August 2013 - 05:11 AM

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.

 

My thoughts exactly. I was wondering why Yrjö mentioned the y axis. Only problem I see is in a multiplayer game with multiple players. I'd draw ThisPlayer absolute last and OtherPlayer entities in some set or random presequent order (doesn't matter since this always looks the same for every player, unless you're making a same-screen game.

 

Personally though, I'd refrain from making a Multiplayer game as my first major project if I were you, in fact I intend to. I want to get everything about my Java skills sorted out before I start doing the dreadful business of networking and maintaining that (both in-dev/alpha, beta and post-release). Just a thought, but if you insist and you got some background in networking (which it sounds like you do) then just go for it. Good luck. smile.png


Edited by Malabyte, 10 August 2013 - 05:21 AM.

- Awl you're base are belong me! -

- I don't know, I'm just a noob -





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS