Whats an elegant implementation for 2D collision detection in a block based game?

Question

to make things clear, i do not want to know HOW to implement collision detection mathematically. What i am looking for is an elegant way to check for collisions without having to manage seperate lists of objects, maybe for example implementing a ICollidable interface.

currently i have a simple gameloop

while(runGame){ handleInput(); update(); render(); }

So there are two possibilities which come straight to my mind. First, ill add an extra call to a method or class handling collisions.

while(runGame){ handleInput(); update(); checkCollisions(); render(); }

Second, every gameobject gets a list of nearby other objects in its update method. so it can do the collision on its own

while(runGame){ handleInput(); update(otherNearShapes); render(); }

i dont like both of these for two reasons.

in the first, i have to manage a seperate list of objects which implement an ICollidable interface.

in the second, the update method handles more logic than it should in my opinion.

so, is there an elegant way of integrating collision detection in my game (loop)? searching the net always only results in how to calculate stuff, but thats not what i want to know.

Answer 1

I can only comment in a answer because of rep but I wanted to say your question is a little vague.

I mean say your have 2 lists, one for all the static blocks that are not going anywhere and another for entitys in your game. You could give your collision class a hold on both lists and then check all of them based on where they are ect, but then your be checking everything in them lists all the time.

If before your level started, your collision class made its own list of static blocks and checked what blocks can be reached by entitys and put them in a list of its own then you don't have to check every block in a area agaist what ever entitys are near by and your render() and update() method can still run thorugh a complete list of all the stuff in you game.

Sometimes more is better and as for the update() method having to much logic, maby you can split up what is going on in there. Like moving all your user input code to another class so its no so crowded in there, more calls to other objects that handle this and that instead of many methods in one space.

Sorry for spelling and grammer, its very late and im very tired

Answer 2

Your "update();" call is itself a request to increment the state of the simulation. This generally involves physics.

Physics usually has some form of "broad phase," which roughly is in charge of figuring out those "other near shapes" and performing collision and physics resolution calculations appropriately. You shouldn't need to pass such a list in, since physics figures that out on its own, generally by using some form of spatial partitioning. In Minecraft-esque games, the "chunk" is a perfectly reasonable large-scale partition. Objects can at most interact with other object only in the same or (if on the very edge) adjacent chunks. You could break a chunk down into even small sub-chunks to make things smaller still.

The game state update steps asks the collision system to generate a list of contacting/colliding pairs of objects, then asks physics to resolve those collisions, then tells objects that need game logic updates to tick (generally just AI and the chunk object in this style of game, since individual blocks have no update logic to run, nor do items). Simpler games, including a Minecraft-ish game, could combine collision and physics, since "physics" in this case just means ensuring that objects don't move through blocks. A tile-based game usually breaks these down into two steps, one for object-tile collisions and one for object-object collisions (these are generally two totally different algorithms, and you often want the object-tile collisions to be checked for and resolved after object-object collision, so objects can't push other object into unpassable tiles).

There's no need for each object to have an individual update() method, nor do you want one. There's a step where you tick the AI for all relevant objects (because your AI system keeps a list of all AI objects and can iterate over just those in one pass), generally after all collision is done and other world-changing updates happen. For blocks, even in games like Minecraft where they can "grow" or otherwise change over time, you do this by ticking the whole chunk as a whole. The chunk iterates over all its blocks in one small, tight loop, using simple random chance to make things happen over time (do NOT store a timer for each block; this is massively wasteful). Items likewise can be despawned by keeping them in a queue; there's no reason to update() each object individually, rather just process the global (or per-chunk) item despawn pool in one pass.

Note that you never have need for interfaces like ICollidable, though you likely have some form of concrete component class for collidable objects. The collision system keeps track of all collidable objects itself and using that spatial partitioning can find all such objects which might be colliding with another. Really though you never need to ask "find all objects that might collide with the player." Instead, collision just does all collision for each object, which naturally includes the player and NPCs. Game logic can then respond to the collision messages, either as they're generated or in another pass (buffering up the collision messages).

Roughly speaking (since being exact here is impossible, as it depends on the specific game), update loops typically look something like:

while (running):
  pump system message queue
  send rendering commands for "last" frame to GPU with interpolation parameters
  integrate physics for "next" frame
  check collisions
  resolve physics
  update world state
  update player actions from input
  update AI
  GPU flush + swap buffers

Again, different games have different steps and ordering. Hobbyist/student games tend to do all rendering at the end of the loop since that's how the old pre-modern-GPU "textbook" game loop is taught. You'll notice that there is no discrete "update" step, though one could collapse almost all of the middle steps into such a step.

I find it useful to have a "tick_simulation()" function as part of a fixed timestep loop. It also lets me turn off automatic simulation updates and then increment the whole state by one step on a keypress, which is a very, very handy debugging feature to have in game, especially for physics.

Answer 3

Well, here's the most elegant alternative I can offer, and it's in fact what I'm using in my games:

Supposing you have a mother-class Entity from which all your classes derive, you could have a static list of Entities called Collidable (preferrably a hash map, so that through a key you can delete the Entity from it when, say, the object dies in your game). In every class that you want to be able to interact through collision, be it a Player, Car or MonsterTree class, in its constructor you can add the instance to this list. As in, Collidables.Add(this).

And in the Entity-based class, you override its Update() method in the following way:

override void Update() {
    // Do stuff

    foreach (Entity collidable in Collidables) {
        if collidable.CollidesWith(this) {
            // Handle the collision
        }
    }
}

It still uses lists, and I'd recommend using an interface for the collision-checking method. Nevertheless, I find it to be a much more flexible way of handling collisions than straight away checking it in your Main Game Loop - by leaving it to the objects themselves to deal with it -, as it easens tinkering with the Main Loop's architeture and prevents the unnecessary checking by Collidables that don't actively trigger collisions.

---

edit:

To adjust this design to what you want, you could use the following technique, then:

Let BasicPack be a basic, abstract data structure akin to void* of C and C++, if you're familiar with it, for it will have almost the same use of void* in these languages.

From BasicPack, you can create various kinds of different Packs, each of which will store specific data. Now, instead of Update(), your update method will be Update (BasicPack args). I'm going into details a little later.

Supposing you have a CollidablePack derived from BasicPack, which has a List of Collidable Entities, you can easily call the Update of each of your Entities in the group you separated as:

    CollidablePack collisionArg = new CollidablePack(YourListToPass);

    // ...
    selectedEntity.Update(collisionArg);

And now, I your update method would look like this:

    void Update (MyPack args) {
        // ...

        // Unwrap,
        CollisionPack collidablesPack = args as CollisionPack;
        List<Entity> myCollidables = collidablesPack.Content;

        // and use as you like!
        foreach (Entity collidable in myCollidables) {
            // ...
        }
    }

Now your instances are pretty much independent from global lists, and we just made things even more flexible.