It’s amazing because yesterday night I re-installed my old Might and Magic 3 to have a feel of old-school 3D. Prelude of the Chambered is more on the Wolfenstein side, but that’s a perfect timing.
Here, have a glimpse of how a real coder (not me) works:
Youtube link: Creating Prelude of the Chambered.
It should be quite possible to render Infiniworld with such a 3D engine. It’s actually one of my goals for Infiniworld 2 or 3 :].
Edit, later that evening:
I died, I was so close! I got lost on my way back from the temple, the ghost boss running after me while I had only 4 health points left. Now I’m scared.
With my previous post regarding the game loop, I wrapped up the basics of what could become a game. It has physics, interactivity, display. However, technical demos are not very interesting to download and run. I thought I should craft a very simple game using the primitive engine I have built. That game will have very little to do with Infiniworld, but it will serve as a proof of concept: this engine can support a game. So let’s do that.
You play as a bunny in a post apocalyptic world. The only place where carrots still grow are in cemeteries because of their fertile soil. However, zombies grow in cemeteries too, especially zombie foxes. They are a bit slow and a bit dumb, but they are legions. You hop and run between your foes and try to gather all the carrots before too many zombie foxes hit you. Fortunately, the radioactive carrots give you strange abilities. With each carrot you eat, your super bunny mind can create a telekinetic shock wave that will repel and maybe even kill the zombie foxes (that’s for using the physics engine :p).
Let’s see how you long you can survive ! Don’t become a zombie bunny.
And let’s code that :D.
In the previous post I explained how I implemented the equations of motion using a RK4 integrator, a Particle class and a couple of Force classes. That was the easy part of the physics engine, for the fun begins now \o/.
Collision detection in games is a big topic. Such a big topic that people have written books about it (I didn’t read them though :p). Fortunately, we do not need to apply these complex models. First, we are in 2D and that simplifies a lot of things. Then, our entities are atomic, not made of fingers and eyeballs that can be sent flying all over the room independently. I won’t be doing this or that. Even what you saw in the Pacman video I posted earlier is beyond my scope since I am not even sure I want to care about rotations.
Everything that moves in the world of Infiniworld is called an Entity. Since they are the only things moving, they are the only things that can collide with anything else. An entity can collide
- with another entity,
- with a tile (some tiles represent walls),
- or with a placeable object.
Placeable objects have not been implemented yet. They can be a chest on the floor, a chair, a boulder, a pillar, a sign…
I am facing a potentially big variety of shapes and I don’t like that at all. If I don’t limit myself, I will still be working on that next year. So this is what I came up with :
I searched the tubes for quite some time in order to find a nice game image but I couldn’t so I made one myself :D. You can see the grid in black, it shows the border of the tiles. It’s grass on the floor, and in the bottom-left corner it’s grass too but it’s on top of a steep cliff so it’s brighter (closer to the sun you know) and you can’t go there. There is a chest for some reason. The chest is not a tile, it’s on a tile. And there are two friends hanging out.
The boundary boxed that I chose are:
- squares for the tiles,
- circles for the entities,
- rectangles or circles for the placeable objects, depending on how they look.
Please note that I do not circle the entire entity sprite! If you see a circle, imagine that in fact it’s a cylinder extending upward; the guy is completely in the cylinder. I should have drawn the circle for the spider a bit lower, and the circle for the guy should be smaller. But you get the idea. Likewise, the sprite of the chest is not entirely within the boundary box, you could approach it from behind, and it would mask your legs. It’s almost 3D!
Some entities will be huge, wider than one tile. That’s cool because it means you can hide from them by running in narrow passages.
The placeable objects cannot be placed freely. They place themselves on a tile according to their design. For example, the chest is centered on the tile. A long table, several tiles long, will have to be made from several placeable objects.
The reason I am limiting the placeable objects that way is because it helps me making sure the game is winnable. If you cannot cross the room because it’s cluttered with stuff, you have a poor game experience. At the moment of checking the winability of the game, I will consider that a tile with a solid placeable object is totally unwalkable even though you could actually squeeze yourself through stuff: better safe than sorry.
So we have to check circles against circles, and circles against square/rectangles.
Circle versus circle.
Testing the collisions of two circles is the easiest of all. All you have to do is to compare the distance between their centers with the sum of their radii. If the distance is greater than the radii, nothing to worry about. If it’s equal we have contact. If it’s smaller we have a collision and that must be solved. I do not really know what to do with contacts yet… For now I’ll consider that a contact is an absence of collision and that’s it.
Circle versus rectangle.
We have many more tests to do now. A rectangle is made of four edges and four corners. You can collide on any of these. Since you are an entity, your boundary is a circle. When I speak about your distance to something, I measure that distance from the center of the circle. So if your distance to a corner or an edge is smaller than your radius, you are colliding something.
Testing eight features per tile is going to be way too expensive from a computation point of view (remember that the maps have about 16000 tiles and that we run the physics 20 times per second). The first thing to do is to prune the tiles: only test against the neighboring tiles. That’s a quick pre-selection to reduce the tiles to test to a maximum of 9 (maybe more if the entity is bigger than a tile). After that, we can make things easier still.
Ever heard of Voronoi diagrams ? They’re perfect for us here. After all, we can only collide against the closest feature. On the figure above, the gray lines delimit the Voronoi cells outside of the rectangle. All the points of the cell where the circle A lies are closer to the left edge than to any other edge or corner. Likewise, the all the points of cell where B lies are closer to the top-left corner than to any other corner or edge. So, instead of testing 8 features per rectangle, we only test 1. That’s a good thing. Finding the Voronoi cell you are in is a trivial matter, just compare your x and y with the two x and two y of the rectangle.
Another simplification arises: if two solid (wall/cliff) tiles are touching by an edge, then there is no need to test the two corners they have in common. Just grab a pen and some paper if you don’t believe me. If you have to test a corner more than once, you don’t have to test it at all. Sweet.
A priori and a posteriori collision detection.
There is a very well explained paragraph on Wikipedia on the subject of a priori and a posteriori detection. We’ll settle for the easy one: a posteriori. This is enough for games anyway. It is way, way, way, waaaay easier to implement. It has some disadvantages but they’re worth it. First, we lose some precision, but that’s not a problem because we’re a game, not a scientific application, and we just need a result that’s good enough to be believable. Don’t forget I approximated you with a circle. The second disadvantage of the a posteriori detection is that if you are fast enough, you can go through objects. Let’s do the math:
Let’s say that the radius of the circle of our entity is 0.5 m. And let’s say that our entity is close to the edge of a tile but does not touch it yet. If during the time step to come it moves by 55 cm toward the edge, then the center of the circle will be inside the rectangle, missing the edge completely.
The physics engine runs at 20 Hz. That means that the time step is 1/20=0.05 s. Moving 0.5 m in 0.05 s corresponds to a speed of 10 m/s. If an entity with a radius of 50 cm moves faster than 10 m/s, some collisions can go undetected. The smaller the entity, the smaller the critical speed.
You may wonder why I cannot detect that the center of the entity is inside a forbidden tile. Well, I can detect that, but what do I do then ? Shall I push the entity outside the closest edge ? What if behind that edge is another forbidden tile ? What if that edge is on the wrong side of the wall and you just quantum-tunnelled yourself through ? Messy. It is wise to keep speeds reasonable.
However, 10 m/s is still not very fast. The game screen you have seen on screenshots is 13 meters wide. Crossing the whole screen in one second is fast, but not ridiculous. I can imagine some nasty fireballs traveling at that speed. How can we have good collision detections with fast objects ?
It’s easy: we just have to rerun the RK4 integrator with a smaller time step. If at the first run the entity moved by more than its radius, then the movement is canceled and instead we run the integration with a time step divided by 2, or 3, or 4, depending of the number of radii you moved. We run it 2, 3 or 4 times to compensate. We test for collision after each and we stop at the first collision we find. It’s very fortunate that we have chosen to integrate with RK4 because this integrator gives the same results for a wide range of time steps.
I’ll write about my plans for the collision response: what to do when entities are bumping into stuff.
It’s almost 2am, my eyelids are violently colliding. I go crash in bed. Bye !
Would you like some science with your game?
Not too much science now, since we are focusing today on physics only. And within physics, on mechanics only. Of the classical kind only. With a focus on dynamics only. And within this, of rigid bodies only. And all that in 2D only. This is a very tiny bit of science so we should have it implemented and tested by Monday, right? Right… -_-
Classical dynamics describes and predicts the motion of bodies under the influence of forces. If we model the legs of your in-game character by a ‘walk force’, then you can change the amplitude and direction of this force by pressing the WASD keys and see your character respond to it. If you’ve had a look at the code pushed on GitHub you might have noticed that the MoveCommand event has a force parameter. It is properly generated by the PygameController, but it is stupidly used because there is no physics engine:
class EntityModel(......): ... def moveTo(self, pos) """Set the position of the entity.""" self._pos.icopy(pos) self.post(events.EntityMovedEvent(self.entity_id, self._pos)) def onMoveEntityRequest(self, event): if event.entity_id == self.entity_id: self.moveTo(self._pos + event.force)
So what we are doing here is , which is as far from the Newton equations of motion as you can get while still kinda move in the right direction.
Introducing the time step.
If we try to copy-paste the equations of motion into our code we hit a wall: physics is continuous, but our simulation is limited to using a time step. The time step is the in the equation above. In real life, that time step is tiny, so tiny we can say it is infinitely tiny and we can use calculus to solve the equations of motion exactly, at least in simple cases.
But a game is not simple: there are many bodies moving around at the same time, many forces applied on them at the same time, plus all the collisions that can occur. Solving the equations exactly is out of the question so we have to satisfy ourselves with an approximation that we can compute with numerical analysis.
The smaller our time step, the better the approximation. There are at least two limits to that statement:
- The precision of the floating point calculations is not infinite. A tiny time step can lead to differences in position or velocity that can hardly be represented (if at all) by a 64-bits float. Then your simulation explodes.
- The smaller the time step, the more computations we need to make. If you divide the time step by 10, you have to run your physics engine 10 times more to get to the same time. There is a limit to the number of computations that our computers can do in one second and if we use small time steps then our simulation is going to run late. If it takes you 0.02 seconds to compute the equations with a time step of 0.01 you’ll never catch up and the game will look super slow.
What do the equations of motion look like when we discretize them with a time step ? Well, there are a bunch of possibilities. They are all equivalent with an infinitesimal time step but they won’t be equivalent for us:
# Possible implementation: position += velocity * dt velocity += acceleration * dt # Another implementation: velocity += acceleration * dt position += velocity * dt # Yet another one: position += velocity * dt + 0.5 * acceleration * dt * dt velocity += acceleration * dt
These are all variations of what many people call “Euler integration”. I don’t know why it’s called after Mr Euler since anyone who starts writing his/her first physics engine comes up with one of these. They just feel very straightforward and natural.
Euler integration works decently in some cases. However, it depends a lot on the choice of the time step. Indeed, with that integrator, the acceleration and the velocity are considered constant during the whole time step. That does not make sense: if the acceleration is constant (and not null), then the velocity CANNOT be constant during the time step. That’s the very definition of accelerating. Different time steps will give very different results and you are forced to use a small time step in order to have the best predictions you can. Which is bad, because small time steps force you to compute more.
Verlet and Runge-Kutta integrators.
Fortunately there are other integrations methods around. They are more complex, less straightforward, but not more complicated. For example, Minecraft uses a Verlet integrator. Another popular integrator is Runge-Kutta. There is a bit of a holly war on teh tubes about which one is better and it’s a bit hard to choose. So let’s apply science, shall we?
- Google scholar for “verlet integration” yields 16300 articles.
- Google scholar for “runge kutta integration” yields 78200 articles.
Therefore Runge-Kutta is better than Verlet :D.
Both Verlet and RK come in several flavors. However, from what I’ve seen around the tubes, what people often mean by “Verlet” is Position-Verlet, and “Runge-Kutta” is most of the time referring to Runge-Kutta-4.
You can have a look at the following articles:
- Verlet Explained: A Simple Time-Corrected Verlet Integration Method, by Jonathan “lonesock” Dummer.
- Runge-Kutta (RK4) integration for game physics, by Kai.
The idea behind position-Verlet is to not use a velocity vector at all. Instead, the velocity is implicit: that’s the distance between the last two positions divided by the last time step. This has the enormous advantage of keeping velocity and position in sync. The algorithm is also very light, it’s almost as light as Euler from a computational point of view. Verlet also lets you rewind a trajectory; that time-reversal symmetry is a nifty thing that has its uses in particle physics but I can’t think of a use-case in a game. Also Verlet is good at conserving the energy of the system, which is cool for serious simulations but we don’t care about it in games where external forces (those damn players keep wanting to move their characters) apply all the time.
The idea behind RK4 is to sample the velocities and accelerations at different times within the time step and make use of Newton series for doing its magic. It’s way less easy to grasp, and there are many more computations involved.
Yeah, Verlet is cool. However, I find it a bit weird. Indeed, how do you start it? You need at least two positions to begin with. Of course you can always say that they are equal, that’s easy, but then all your objects are created at rest which may not be what you want. Perhaps it’s enough: the arrow is at rest in the bow and the force of the string is applied only once when the arrow is fired. You’ll have to tweak the force using your time step to ensure that the arrow achieves the same speed regardless of the time step. Another possibility is to use Euler to define the second point. The example of the bow and arrow also illustrates the lack of impulses. An impulse is an instantaneous change of the velocity. Bouncing on a wall creates an impulse: your velocity is mirrored on the wall. With Verlet, just changing the position is not enough to simulate the impulse because your body won’t bounce in the right direction ; instead you have to create a one-time pseudo force that takes the time step into account. Messy.
On the other hand, RK4 lets me do my physics the way I am used to: I have both my position and my velocity. RK4 is very resistant to a change in time step. So even though RK4 is heavier from a computation point of view, I can call it less often. I choose RK4. It’s not even that hard to implement : Integration basics, by Glenn Fiedler on gafferongames.com.
Once I have implemented the integrator, I will have to start the serious business: collisions.
Edit: One hour later…
Wow, that went pretty well. I spent more time writing the post than actually implementing the thing. The version v0.0.4 is pushed on Github, you can pull or and download it already. See my previous post to know how.
Now, I’ll write something about how I implemented it. So little code has changed ! Have a look:
In the previous article I explained how I implemented the event management. Now, our software bricks can talk to each other. Let’s get them to talk ! Well… let’s get them, first. We need bricks. The good ones.
Too often I started similar projects, focusing on an aspect such as the procedural landscape generation. It worked ! But I got stuck. I ended up with an ASCII dump of something representing a world, but I couldn’t do anything with it. There was no game built to explore that world. This time I want to start making the game interactive in the first place: we need to be able to explore before having something to explore.
I chose pygame for managing the input and the output. The input being the player’s fingers on a keyboard/mouse/joypad, and output being the screen and loud speakers reaching the player’s eyes and ears. Because I apply some kind of Model-View-Controller (I always say “some kind” because everyone has his own MVC), I will wrap the input in a Controller, and the output in a View.
We will have a PygameController and a PygameView class. I don’t want to use anything related to pygame in the Model classes, to make sure that when I decide to use a different rendering engine I only have to rewrite the input and output without touching the game logic at all. There will probably many other pygame-related views, probably one view per character to be displayed, for example. These views will be managed by the main PygameView. It would be wise to group everything pygame-related in one single package so that it can be replaced. Other views, like a console view for the server, would be kept in another package.
And, finally, we’ll need a game loop. I’ll go for the simplest game loop ever, but in a near future I shall write a whole entry on the subject.
Let’s get to work ! Very soon, the first screenshot ! I bet you can’t wait :).
The Model-View-Controller pattern is quite a wonderful thing. I had some troubles accepting it because I was born at a time when the most powerful computer in the world had 8 Mb of RAM and a CPU beating at 80 MHz. I still feel a squeeze in my heart when I write an if statement inside a for loop, so I found it hard to accept replacing function calls with messages broadcast all over the place to components that don’t care. To me, it’s like taking all the axones away from a nervous system and ask the hormones to replace them in their job: a tremendous waste of memory and CPU. But memory and CPU are cheap now, and my ambitions are relatively modest from a performance point of view. So I gave in and am now a happy man.
I won’t spend much time describing it because others have done it quite nicely before me. I really urge you to read the following articles if you don’t really know what it’s about.
The idea is to separate the
- game logic –or Models– (physics engine, position of the characters, tiles in the map)
- from the way it is presented –by Views– (sprites on the screen, debugging console, a bit of network code that sends the info to the client who is the one doing the actual rendering)
- and from the way it is controlled –by Controllers– (keyboard, mouse, clock, network sending info from a client or a server).
This makes developing our game a bit like playing with Lego bricks: adding or removing a brick does not interfere with anything. Models Views and Controllers send Events to an Event Manager which takes care of forwarding them to other Models Views and Controllers.
So who controls the Controllers ? The Event Manager does. It also manages the Views and the Models.
For example, the server does not need to display anything, only the client does. So you just delete all the graphic Views from the server code. You can plug a console View that shows the server load if you want. An other example: if you want to replace my PyGame 2D view by some 3D OpenGL magic, go for it. The game logic does not care one bit. This is all very well described in the two articles I linked up there.
However, I would like to add a few things in this post.
Brown’s implementation does not scale very well. It works perfectly of course and has the immense advantage of being very easy to understand, which is exactly why Brown chose this implementation for writing his tutorial. But when you look at it, 1) every Event is sent to every Listener (Model View or Controllers) ; 2) from there, a bunch of if statements will decide how the Listener will react, if it reacts at all because in many occasions the Listener doesn’t even care about that type of Event. Stone me for optimizing early, but it could be interesting to have the Listener specify which kind of events they are interested in (solving problem 1), and give to the Event Manager a direct handle to the code that should react to it, instead of filtering with ifs (solving problem 2).
Both Brown and Koonsolo apply the traditional MVC pattern which allows the View to know something about the Model. For example, the DragonSprite View really has a pointer to the DragonCharacter Model. I don’t think I’ll do that.
The Model sure ignores the View but the View knows about the model. This asymmetry feels dirty to me. It’s almost an invitation to modify the Model from the View, which is a bad thing. But even if you behave, I am still annoyed by having to carry full objects in my Events. For example, the MonsterAppearedEvent will have to carry the DragonCharacter object so that the DragonSprite be created and points to it. That complicates the serialization when you need to carry Events over the network and that makes debugging a mess. First, too many pointers and references: you don’t know who owns who, and if you use WeakRefs in the View to avoid memory leaks you’ll end up with broken pointers. Second, when you print an event into a log file it doesn’t help you at all because the CharacterMovedEvent does not tell you where the character moved ; indeed the View just has to look into its model to get the info. Third, it becomes difficult to test the View without testing the Model itself.
Does the Sprite really need to know the whole Model ? Of course not. If the Model moves, then the sprite just needs to know the new position, and this position can be stored into the CharactedMovedEvent.
One advantage I can see when one sends the full Model is that the View can initialize itself in one go. When the View is created, it knows already everything about the model and can display it properly at the right place. But we can also do it with events. You can have the CharacterCreatedEvent contain enough info for the View to initialize itself. And if it’s still not enough, the View can post a CharacterPositionRequest Event and wait for the Model to answer with a CharacterPositionEvent Event.
What I’m going for is not traditional MVC, I’ll use Events all the way. Which means that there is no real difference between a Model, a View and a Controller, at least not from an implementation point of view. They’re all Listeners, waiting for events to tickle them and posting events when they feel like it. However, what I’m not doing, is having all the Models talking to each other through events. I want to separate Model, View and Controller, I don’t want to separate the model from itself unless there’s a very good reason to do so. Can’t think of any right now.
So I’ll be working on that. I’ll tell you when it’s pushed on GitHub!
I decided to call my game Infiniworld, which I can’t pronounce properly because I’m French. There are a few hits on Google for that word but I don’t really care as they don’t seem important *grins*. One of the hit is actually a GitHub repository by me ! Which I am going to wipe out veeeery quickly because it’s totally outdated, ugly, empty and you’re going to freak out. And then I’ll recreate it again, clean and all, for you all to look into as we progress.
Infiniworld is a very generic name for a game. It’s because it’s not just a game, but a game that lets you take part in its creation, creating new experiences and therefore new games. Infiniworld can make many worlds, probably googolplexes of them. I may do the maths one day but until then it’s safe to assume that infinity is the exact number.
As I mentioned in my previous post, the world of the game is procedurally generated. It is not new:
- The world of Daggerfall was procedurally generated at Bethesda’s HQ and then burnt onto the CD, ensuring that all the players had exactly the same world. I don’t want that. I want the players to be able to create their own worlds.
- Minecraft generates the world on the fly as you explore, but it’s not like you can choose what’s in it. You can edit it, but you cannot say in advance that you want to play on one tiny island. However the game lets you choose a seed, and if you enter the same seed you should get the same world. I want to do more than that.
- Fuel makes pretty landscapes for you to drive through. It does not generate scenarios or quests.
- Nethack’s dungeons are procedurally generated, but it doesn’t care about the game being winable or not. I was stuck once on level 1 in a closed room with no secret door and no tool to dig the walls. I want to do better: not just a dungeon but a world as well. And to be frank, Nethack is silly. I love it, but what a mess…
- Diablo: same story, all the time.
- etc, etc, etc…
Procedural generation is often limited to the landscape. I want to push it further. We could push it to the max and have even the textures and the music procedurally generated, as well as the game play, the user interface and absolutely everything, but that’s a job for a titan. I want a middle ground: generate the landscape AND the adventure taking place in it. The scenario will be procedurally generated.
One game will be about bringing hard-to-come-by precious resources to some kingdom so that it does not need to invade yours any more. The next one will be about killing that bitch of a princess and free all the dragons. Another one will bring you through the Swamps of Pestilential Doom to the necromancer who will resurrect your uncle so that you can torture him into revealing where he hid his fortune.
See where I’m going ? There is probably some way to generate a story from story-bricks. You have one main objective, and to get there you need to go through many steps. It does not need to be linear, there can be branches, there can be several ways of ‘winning’. We are going to write the algorithm to create the story from the story-bricks.
Which leaves us with the question: who will create the story-bricks ? Me, you, anyone who can program and write a script for Infiniworld to import and include in its database.
Many elements in the game will be part of that database: equipment, items, monsters, playable characters, story, quests, puzzles, tilesets, sound effects, dungeon layout, dungeon rooms, shops, planet, magic spells, etc.. It should be possible for the players to create their new game elements and exchange them with their friends. Then Infiniworld picks some of these elements, letting the player choose some (we don’t want to spoil all the surprise do we?), and shakes it all together to come up with a brand new game. Want a ten minutes solo adventure or an epic 70 hours multiplayer saga ? Infiniworld will give you just that.
Indeed, getting started is the easy part. What’s really tough is to keep going till it’s finished. I’m not talking about the blog I’m just starting to set up, gosh no; the blog is just a tool, a gadget, a by-product of the Great And Amazing Project.
Amazing the project is indeed: we are going to build a computer game. It is going to be wonderful. Each step of the project will bring so much satisfaction and delights that the end product will be nothing less than orgasmic. Convinced ? Let’s get started then. And let’s finish, at some point.
The game we are going to build here will be seen from above, like the old Zelda games. I don’t want to dive into 3D because I’ve never done it before (well YES I did, but before 3D video cards existed. Remember Doom ? I did stuff like that a bit). I want to retrieve some of the feelings I had when I was playing Daggerfall: vast world, lots of exploration and freedom, one main quest with several branches, many quests, dungeons, towns, castles, role playing, inventory/resources management, etc.. And I want it multiplayer so that I can play with my friends.
But mostly, I want it:
- procedurally generated
- according to the players wishes.
Procedural content is the holy grail of game development. I want to be able to sit in front of my computer, run my game and ask it :
“Please make me a medium-size world with ten dungeons. I want a lot of islands. And no orcs, I can’t stand orcs anymore so just no orcs in the game, same for goblins, none at all. Go easy on the puzzles, and super easy on the fighting because I mainly want to explore and don’t want my ass kicked this time. And oh yeah, do use this new ‘spider caves’ tileset my friend photoshopped for me, and this Spider Queen monster that I scripted.”
and press the “Let there be light.” button.
Wouldn’t that be grand ?