4
\$\begingroup\$

I've been a programmer for over a decade, professionally for the last five years, but I've never really done any games programming. I've had a look at some tutorials but most of what I've found is geared towards people with no programming experience, so I've tended to get bored and moved on. So, after grasping the basics of the game loop, I've decided to dive right in.

As my first project I am programming a basic 2D top down maze game (a Pac Man clone). I've got all the basics working fine, and am now thinking about optimizations. I have an idea to improve the performance of my wall collision detection but I'm interested to know the 'proper' way of doing it.

At the moment my algorithm is basically:

  • Check direction player wants to move in
  • Loop through all walls and see if any are at that position
  • If there are no walls, move the player

This is working fine, but I imagine if I scale it up that the act of looping through all the walls each time will become an issue. Due to the simplicity of the game and the speed of modern computers, it might not ever be noticeable, but I'd rather be using the cycles for something else.

So it occurs to me that as this data is never changing, I could just build a lookup table as part of my map creation within my level editor. I've heard about similar things being done for more complex 3D games. I would then have a lookup table that stored each possible player position, each possible direction, and whether the player can move there. This means that on each move, I can just do a quick check to the lookup table to see if the move is possible, rather than repeatedly looping through a load of static data every single frame.

Is this a common thing to do? Or are neither of these approaches any use, in which case what is the best way to handle this?

\$\endgroup\$
  • 1
    \$\begingroup\$ Creating a navigation mesh would be an optimization, but it looks like premature optimization to me. You have a solution which works - be happy about this and move on with implementing your actual game idea. You can always improve it later when you indeed find a useful purpose for those CPU cycles you gain. \$\endgroup\$ – Philipp Jun 25 '15 at 20:25
  • \$\begingroup\$ As I say, I have most of the game elements in place. But then again, I'm unsure if this is ALWAYS going to be premature optimization, if it is just overthinking things. I suppose the core of what I want to know is - how would this be implemented in a professional game? Additionally, the original Pac Man ran on very primitive hardware, so I'm interested to know how this was handled then. \$\endgroup\$ – razethestray Jun 25 '15 at 20:27
  • 2
    \$\begingroup\$ When you are not sure, it very likely is premature optimization. Take care of the problem when you actually have it. In the meantime just be careful to not have the rest of your code coupled too tightly with the functionality to make it painful to replace it later. But when you encapsulate your code properly, this should not be an issue. \$\endgroup\$ – Philipp Jun 25 '15 at 20:29
7
\$\begingroup\$

Lets start with general rule of optimizing things, especially when it comes to games: Profile it. It's not worth working on something that works already, because especially with games, you will get stuck optimizing and refactoring what you have, instead of doing actual work.

When a player is playing a game, they usually are doing just that, because a game requires most attention, especially as this will only get called when the player is moving, so the CPU cycles you save are not needed for anything else.

But lets put that aside, this is a learning project, so you want to try what can you do.

The idea you describe has two big negatives:

  • While it scales well on CPU speed, it scales very badly with memory.
  • It doesn't support floating-point locations or moving directions, which are what you should be using for a smooth experience.(Well, its not a must, but very common)

Lets get to the part: Do they use this? Probably not, at least not like this or for this.

Do they use something similar? Definitely! The answer is in spatial data-structures which let you get a list of only the nearby walls from the player location. This is done in 2D using Quad-trees or BSP usually. In 3D with octrees and BSPs.

What is the best way to handle it? The best way is to get it to work, and when it starts to eat your CPU cycles(You know, because you Profiled it), come back and optimize it.

\$\endgroup\$
3
\$\begingroup\$

Fun fact: I used to work for the company that made Pac-Man.

Anyway... how are you storing the wall data for your maze? Are you using a tile map? (Relevant: Wikipedia entry on tile maps). If not, you should consider it because one of the biggest benefits to using one is the ability to detect walls purely by looking at the contents of (x, y) in the array storing the tile data.

In other words, you're kind-sorta using a lookup table as you mentioned, but with the ability to go to the exact spot you need to check.

For example, if you had a 10x10 tile maze, you would have a 2-dimensional array where 0 would be an open square and 1 would be a wall. Then, once you determined the tile the player was moving to you just check if tiles[playerDesiredPosX][playerDesiredPosY] == 1. If it is, don't let the player move there.

Even if you're working in 3D and not using a tile map as the data structure representing your world, you can still add one purely for the collision data of the "floor" layer that the player moves around on, especially if the walls are squares/cubes/blocks.

So, yes; precomputed. Especially if the walls don't move.

\$\endgroup\$
  • \$\begingroup\$ +1. This is the method I use for my maze generator, and I'd say it works pretty well, as collision for a 50x50 maze runs just as fast as a 2000x2000 maze. \$\endgroup\$ – Superdoggy Jun 26 '15 at 0:28
  • 1
    \$\begingroup\$ And note that even if a simple tile map can't resolve whether there are collisions or not the idea is still useful--divide the world up into tiles, each tile containing a list of the walls in that tile. This reduces the calculation to constant time no matter how big your world. \$\endgroup\$ – Loren Pechtel Jun 26 '15 at 3:15
  • \$\begingroup\$ And you can note that this is also one of the possible spatial data structures, one that I didn't mention. \$\endgroup\$ – akaltar Jun 26 '15 at 5:26
  • \$\begingroup\$ It's also the way that Pac-Man and nearly every retro maze game in existence does it. \$\endgroup\$ – Sandalfoot Jun 26 '15 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.