Sign in to follow this  
Aztral

Using a grid

Recommended Posts

I'm using a grid to implement the world in my game. The grid is used for path finding mostly and a few other things. My question comes because the world is rather large (my grid is something like 800x600) which obviously uses a ton of memory and doesn't seem all that efficient. This means that when I scroll the world I have to move 480,000 different squares. Is there a better way I can be going about using a grid?

Share this post


Link to post
Share on other sites
you can break up your grid into sections and only deal with the current section of the grid (or neighboring grid cells if you get near an edge or a corner).

Im confused though when you said "I have to move 480,000 different squares".

Why do you have to move them? move the player, not the grid, right? (unless I'm missing something)

Share this post


Link to post
Share on other sites
I have to move all the squares when the world scrolls. If the player is "moving" right, the world scrolls to the left. I have to move all of the squares representing the world.

I'm not sure how I can split up the grid and only use pieces of it at a time. For example if I wanted to I could tell the player to move from one corner of the world to the other, in which case I would need to know about the entire grid for path finding purposes.

Share this post


Link to post
Share on other sites
Quote:
Original post by Aztral
I have to move all the squares when the world scrolls. If the player is "moving" right, the world scrolls to the left. I have to move all of the squares representing the world.

I'm not sure how I can split up the grid and only use pieces of it at a time. For example if I wanted to I could tell the player to move from one corner of the world to the other, in which case I would need to know about the entire grid for path finding purposes.


try to limit the amount of distance your path finding is required to do, ie don't let something travel from one end of the map to the other. Google quadtree's or portal maps, most of the design are meant for 3d but can be helpful in comeing up with ideas to splitting your world up into manageable sections.

And I'm not sure what you meant by you have to move the entire map when your character moves?

Also when it comes to pathfinding, you could take your sections and look at them like a grid, what sections will the player move through in order to make it from one point to another, and only load those sections.

Share this post


Link to post
Share on other sites
I'll look into those, thanks.

Regarding moving the entire world:

Say one grid square is initially at the point (10, 10) on the screen. Now say I want to scroll 5 pixels to the right. If I scroll the world 5 pixels to the right, then that square is now at (5, 10), correct? I don't know how I can move the world on the screen without modifying each square's x,y screen coordinates.

Share this post


Link to post
Share on other sites
Quote:

Also when it comes to pathfinding, you could take your sections and look at them like a grid, what sections will the player move through in order to make it from one point to another, and only load those sections.


Ok but then it seems like I'd be loading/deallocating big chunks a LOT of the time.

Also, say I wanted to have a minimap, and when I click on a location on the minimap the "camera" zooms to that location.

Do I have to load big chunks of the world when I want to scroll/zoom to a different location?

Share this post


Link to post
Share on other sites
Quote:
Original post by Aztral
Say one grid square is initially at the point (10, 10) on the screen. Now say I want to scroll 5 pixels to the right. If I scroll the world 5 pixels to the right, then that square is now at (5, 10), correct? I don't know how I can move the world on the screen without modifying each square's x,y screen coordinates.

What graphics API are you using? OpenGL, DirectX, GDI, etc? If you are using OpenGL or DirectX you can "translate" the grid which is more efficient that moving each square at a time. Or, similarly, you can move the "camera" which is basically the same as translating.
Please note that i am not an expert at graphics so my terminology might be a bit off.

Share this post


Link to post
Share on other sites
Associate coordinates with your player, and change those when you want to move around. Render the world with these coordinates in mind, i.e., the camera follows the player.

Pseudo-code:


class Player {
// Location in the world space
int x, y;
}

function World.Draw(Player focus) {
for(int x from -screenWidth / 2 to screenWidth / 2)
for(int y from -screenHeight / 2 to screenHeight / 2)
// Check if this offset location is valid
if(IsInWorldRange(x + focus.x, y + focus.y))
// Retrieve the offset tile from the grid, and show it at (x, y)
Draw(world[x + focus.x][y + focus.y], x, y);
}


This can of course be orthogonal to any chunking you add to map loading. Make chunk sizes some reasonable multiple of the amount of tiles across/down that can be displayed on a screen at once. You would need at most 4 chunks in memory at one time (when the camera was positioned at the corner of a chunk boundary).

Share this post


Link to post
Share on other sites
Thanks for the replies everyone.

Is this a reasonable solution?

- In my GridNode object I will have two static integers dx and dy, which reflect the x change and y change in the world on-screen location.

- I will make a quadtree to split my world up into manageable chunks and before I render a frame I will check if I need to worry about drawing each chunk.

- If I do need to worry about a specific chunk, I will update each GridNode in that chunk such that it's x and y reflects it's current dx and dy.

This would be considerably more efficient than modifying every single GridNode in the grid so that it's x and y reflect the world dx and dy every frame, right? As mattd said I'll only have to worry about 4 chunks at a time.

Share this post


Link to post
Share on other sites
Nooo :) When the player moves, the only coordinates that should need to be changed are... the player's!

Try looking at it in 'world coordinates', and not 'player coordinates'.

The world coordinates of an object are given relative to some well-defined location in the world (i.e., the top-left corner being (0, 0)).

The player coordinates of an object are given relative to the player.

For example, take an object that is just to the right of the player, but in the centre of a 400x400 map. It would have world coordinates (200, 200), but player coordinates (1, 0).

When all the coordinates of your objects/tiles/players/whatever are given in world coordinates, it becomes trivial to move your player - all you need to change are the player's coordinates in the world. After all, it is the player moving in the world, not the world moving around the player!

If you were using player coordinates exclusively, you would need to change the coordinates of every object (ironically, except the player: it always has player coordinates (0, 0)!)

When the time comes to render the world view to the screen, you need only render the range around the player: a rectangle centred on the player, with width and height being that of the screen. You can get that rectangle generated using something like the pseudocode I gave before.

When rendering, you keep track of both the world location of the tile being drawn, and the location it needs to appear on the screen, making sure to keep these two ideas seperate. It sounds like you're confusing the two currently, making more work for yourself than necessary.

Share this post


Link to post
Share on other sites
Just to reinforce what's already been said, there is almost certainly no reason that you would need or want to move the world (or any part of it) in order to create the effect of the player moving. As has been suggested, move the player, not the world; then, when rendering, set up the rendering parameters (e.g. the position of the 'virtual' camera, etc.) so that the player appears at the center of the screen (or wherever you want the player to be).

Share this post


Link to post
Share on other sites
Quote:
Original post by mattd
Nooo :) When the player moves, the only coordinates that should need to be changed are... the player's!

Try looking at it in 'world coordinates', and not 'player coordinates'.

The world coordinates of an object are given relative to some well-defined location in the world (i.e., the top-left corner being (0, 0)).

The player coordinates of an object are given relative to the player.

For example, take an object that is just to the right of the player, but in the centre of a 400x400 map. It would have world coordinates (200, 200), but player coordinates (1, 0).

When all the coordinates of your objects/tiles/players/whatever are given in world coordinates, it becomes trivial to move your player - all you need to change are the player's coordinates in the world. After all, it is the player moving in the world, not the world moving around the player!

If you were using player coordinates exclusively, you would need to change the coordinates of every object (ironically, except the player: it always has player coordinates (0, 0)!)

When the time comes to render the world view to the screen, you need only render the range around the player: a rectangle centred on the player, with width and height being that of the screen. You can get that rectangle generated using something like the pseudocode I gave before.

When rendering, you keep track of both the world location of the tile being drawn, and the location it needs to appear on the screen, making sure to keep these two ideas seperate. It sounds like you're confusing the two currently, making more work for yourself than necessary.


Hum, ok. So I basically pick a point of focus (the center of the camera?) and render everything within a given rectangle of that. I would need some method for determining the coordinates of the rendered objects.

I don't see how "the only coordinates that should need to be changed are the player's". If I want the world to scroll. That is - I want a tree to appear to move to the left when the player moves to the right, it's on-screen coordinates have to change? How else do I know where to draw it on the screen?

Share this post


Link to post
Share on other sites
The on-screen location of a given object is a function of its world location, and the player's location. Therefore when the player moves, so does the object on screen.

Share this post


Link to post
Share on other sites
That sounds very reasonable, but.. even if it's a function of those values, AS3 might make this difficult.

Once I add a GridNode to the display list, AS3 is drawing it, period. In order to not have it drawn on screen I would have to make it not visible or remove it from the display list, either way that's a LOT of nodes I have to either say GridNode.visible = false or remove from the display list. Granted I don't know AS3 that well, but based on my understanding of it doesn't lend itself to simply not drawing something you don't want to draw. Now, I could adapt my earlier post and use a quad tree and make all the previous frames' visible nodes invisible for the next frame, but it still seems like a lot of nodes I'm having to modify every frame, and along with all of the other calculations being made every frame it kind of has me worried.

To clarify - Basically this would be the solution:

- Determine the screen location of the world object as a function of its world location and the player world location only for those objects in the quadtree that are on the screen.

- As a frame exit event, make those drawn objects from the previous frame invisible (since they may not be in the camera this frame, and since I'm not updating their screen coordinates if they aren't on the screen).

*I might just not have a very good understand of AS3 and I'm making this more complicated than it needs to be.

Share this post


Link to post
Share on other sites
Ah, looks like I missed an important part - using Flash.

Is there no way you can create a 'canvas' like object and render tiles using your own algorithms in Flash?

It looks like the alternative IS moving all the other tile objects around the player, like you originally mentioned >_> (ref)

Note the way that tile objects are reused in the above tutorial - when a tile is scrolled entirely off-screen, its movie clip is (maybe) changed and it is moved straight to the opposite end to be reused, scrolling back in. This means you only need enough tiles in the renderable view to fill your screen, plus enough to handle the scrolling (i.e., an extra row and column's worth).

(Forgive any weird terminology, I don't develop Flash :])

Share this post


Link to post
Share on other sites
Thanks a lot for all of the help. . were I doing it in any other language I'd do it exactly as you mentioned.

I think what I am going to do is disassociate my GridNodes with the display list. I was planning on having nodes be responsible for their own texture, any buildings on them, terrain on them, etc. So I added each node to the display list and then each node added things that were a part of it to the display list.

Rather than doing it like that I will not add nodes to the display list at all - they'll just be used for path finding and some collision checking. I'll move buildings and terrain independently and won't have to do any calculations per frame on every single node.

Reusing tiles like that is a very good idea. . being that the ground texture will be basically identical throughout the game, with buildings/trees/etc. occasionally thrown on top of it.

Again I appreciate all the help.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this