In a game Engine...

Well we are coding a Zelda type clone and I'm still working on my space sim as well. I'm not sure I can do either of these without some type of significant scripting in place to do missions, quests, etc.

Now for something simple you might be able to get away with using functions as script actions but again I shudder at doing this because it really hard-codes you into a corner later on.

At the very least you could implement a variable system and some IFs. A variable system can be implemented by using a class to wrap access to an array of values. It's quite simple and then you use script commands to access and modify the array.

This prevents you from having to create a difficult expression parser which is really not needed for most applications of scripting. We are not trying to re-write the C++ parser here, just something basic.

I understand Bubba, but you must understand that my first games aren't going to be space sims or zelda clones..

They're gonna be like, breakout, arkanoid, pacman, tetris, etc.. Things I can aesily hard code ..

Maybe if I get bored, I'll copy all this down into a pretty diagram for you all to see, actually, I think I'll do that...

http://img.photobucket.com/albums/v1...GameEngine.jpg

And there it is, an example of a simple game engine.

Well, I don't see how there's anything wrong with that. You may find it works beautifully in practice or that you will need to change it.

Regardless, it's clear you're putting a ton of thought and effort into this and I admire that intensely. Keep hacking out code and asking for help (what you've been doing all along). I'm sure you will have something you're satisfied with.

A likely scenario: you're going to code an overly-elaborate layout for a game engine, and maybe someday you'll see the code for mine and realize how much of yours is overkill (which should make you happy, because your layout may end up more intelligible than mine).

This scene graph thing is aching my head, but it is completely necessary..

I understand HOW to create the geometry nodes and such, I understand HOW to update them, and what I need to do to update them..

The thing I don't know is this:

When do we update? When I say update I'm talking about the local transformation of each geometry node. I understand that for static objects, they can just be initialized and then never touched again in terms of local transformation. But for meshes that walk around and animate, their local transformation is changing constantly, and sometimes they are standing still.

My main question is, should I update a dynamic mesh even if it doesn't need updating, say it is in your view frustrum, but is at a complete rest. Do I stop updating the transformation at this point? If I did make it so I could stop updating when an object is at rest, it would save some valuable computing time and skip some unecessary matrix multiplications, but I am not really sure about to implement it .

Any clues?

Update the object and let it decide if there's anything to be done computationally.

Code:

void update() {
  if (!needsUpdate()) {
    return;
  }
  ...update
}

I know a simple boolean value would suffice, but what should I check for to detect equality?

Does new local translation = old local translation?
Does new parent translation = old parent translation?

If no to both of those, update translation and draw
If yes to both, just draw with current translation without multiplying anything?

The scene graph you want to use will be based on your type of engine.

Is your game engine mainly doing indoor scenes?
If yes, then you know your draw distances will be very manageable and thus you can cram a ton of objects into one room and get as detailed as the video card allows.

Good scene graphs for indoor environments:
1. BSP trees
2. Portal culling systems
3. A combination of 1 and 2.

We all know what BSP's are so I will talk about portal culling. Portals are extremely powerful and extremely good at clipping and culling geometry.

It works like this. Find a room in your house and go stand in it. Now the only way you will see any other part of the house is if the door in your room is open and leads to another portion of the house. That door is your portal. So if the portal (a simple quad) for the door is inside the frustum then you must draw the adjoining room. The key is then you compute a new frustum based on the door portal and cull everything in the next room according to that frustum. Now if the next room has a door or window that leads into another area then you check to see if it's in the frustum of the door since this is your new frustum. If it is, then you render the geometry for that room and clip and cull according to that new portal.

As you can see this will eliminate a lot of triangles extremely fast.

To build this system you need a couple of important items.

1. Every portal has 2 sides. This means you must place 2 quads or polygons representing the portal back to back in the doorway.
2. Don't draw the actual portal geometry, it's only used for culling and clipping.
3. In order to clip to the portal, a simple frustum cull would suffice which leads to another type of scene graph.


The type of scene graph you use in the room is up to you but if the geometry is static, I would say either a BSP tree or quadtree would suffice. An octree would be best but only if it sped rendering up. Checking more nodes may actuall hamper performance rather than help it.

The second thing you must learn is how to extract the planes from small portals to create the frustum. It's easy to extract them for the main viewing frustum but it does become a bit more to extract them from another piece of geometry. There are several tuts on the web and several books on amazon.com that discuss this type of system.

The only thing I can come up with as far as updating is a range-based system. Using anything else may result in objects not updating correctly due to the culling/clipping process. We still want the bad guy in the hallway to blow the crapola out of our buds in the hallway, if we are in the room adjacent to the hallway. If we use the portal scene graph system, they will only update when they are visible which is great for FPS, but not good for the feel of the game. Update using a bounding sphere. If an object is within range of the sphere, update the beast. You will have to account for objects that may move in and out of the sphere. You would still want to update these guys. You don't update when the object is and will be completely out of the sphere.

I think you may find that you can update the entire level in memory and not run into problems. Updating is extremely easy and extremely fast, especially if your rendering is optimized to the max. You could forego big time physics calcs for objects that are out of the sphere and only use the physics stuff on objects that are in proximity of the player.

For updating you could use a quad tree but then you must check each object to see if it has left a node and is entering another one.

There are tons of ways to do this, and you may even come up with another way in your pursuits. No one really cares how you do it, just as long as it works.

Outdoor scenes
Outdoor scenes are actually my specialty and area of interest. There are several good papers on www.vterrain.org about how to go about this.

The main scene graph for all outdoor scenes is the quad-tree. A quad tree is very fast and very east to implement.

My structure is this:

Code:

struct TerrainPatchInfo 
{
  int iNumVertsPerRow;
  int iNumVertsPerCol;
  int iNumCellsPerRow;
  int iNumCellsPerCol;
  int iNumVerts;
  int iNumTris;
  int iNumTrisPerRow;
  int iNumTrisPerCol;
  int iMapWidth;
  int iMapDepth;
  
  int iResType;
  int iTreeType;
};

class CTerrainNode 
{
   CTerrainNode *m_pUL;
   CTerrainNode *m_pUR;
   CTerrainNode *m_pLL;
   CTerrainNode *m_pLR;
   TerrainPatchInfo  m_PatchInfo;
   ....
};

class CTerrain
{
   CTerrainNode *m_pRoot;
   ....
};

The code to create it looks basically like this. I have removed the terrain patch resolution code because it's complex and hard to explain here. I've also removed the u,v texture calculation per vertex for the same reason.

Code:

void CTerrain::CreateVertices(CTerrainNode *pNode,int x,int z,int x2,int z2,int iDesiredSize)
{
  if ((x2-x)<=iDesiredSize)
  {
     //Compute how many vertices
     ...
     //Compute cellsize for this patch
     ...
     //Create vertices for x,z,x2,z2
     ...
     //Create indices for vertices
     ...
     pNode->iTreeType=QUAD_LEAF;
     return;
  }

  //Compute midx and midz for split
  pNode->iTreeType=QUAD_NODE;
  int midx=(x2+x)>>1;
  int midz=(z2+z)>>1;
  midz+=z;
  midx+=x;

  //Create upper left child
  pNode->m_pUL=new CTerrainNode;
  CreateVertices(pNode->m_pUL,x,z,midx,midz);

  //Create upper right child
  pNode->m_pUR=new CTerrainNode;
  CreateVertices(pNode->m_pUR,midx,z,x2,midz);
  
  //Create lower left child
  pNode->m_pLL=new CTerrainNode;
  CreateVertices(pNode->m_pLL,x,midz,midx,z2);
  
  //Create lower right child
  pNode->m_pLR=new CTerrainNode;
  CreateVertices(pNode->m_pLR,midx,midz,x2,z2);
}

My actual code creates 3 resolutions of the terrain. The resolution used is chosen at run-time based on distance from the camera. I line up differing resolutions by using a border for each new resolution that consists of one triangle. This way low to med lines up and med to high lines up. Low to High will not line up, but this also will never occur.

This is just an example of how complex these things can get.

As per portal culling, the doom3 map format is easy to read ascii, and there's even a NeHe tutorial on it I believe (or maybe on GameTutorials.com).

Regardless, portal culling is certaily an elegant solution for indoor scenes (but awful for outdoor, obviously).

I don't want an "outdoor engine" or an "indoor engine"..

I want to be able to flow from incredibly complex terrains with waterfalls and mountains, sheer rocky cliffs, to towering buildings, equally as complex as the terrain we just moved from, labyrinths of crypts, etc etc..

To do this I think we need a nice combination of quads trees for terrain, then switch to portal mode once we've entered an "indoor" area..

I guess this is where I start defining MY game engine.

I want large battles, I want to move seemlessly between outdoor computing to indoor computing, I want the defenders to defend their castle from inside, through portholes where they shoot arrows from. I want attackers to be able to invade the castle without a huge loading screen causing problems...

The last thing I want is the player to go "ARHG I died because my screen didn't load fast enough!!!"

Yes you will need quad trees for the terrain and portals for indoor scenes with BSPs as well.

It is NOT easy to both do a good terrain engine and a good indoor engine in the same engine. This is because in one application you are looking for huge vast environments that stretch to the horizon and in another you are looking to cram as much detail as possible into a small room or area. Here is what will happen inevitably.

1. At the doors of your buildings it is possible that both the terrain and some indoor details in your scenes will be visible at the same time. At this point you must use the door to the building as a 'portal' to the outside world and then cull the outside geometry based on that portal. Same holds true for windows in the building.
2. If you don't it is extremely possible that you will exceed the max primitive count for the video card and thus the terrain, objects on it, the building, or objects in it will simply vanish.
This is because the card cannot draw them. You have too many triangles.


Here is what I would do.

• First check to see which buildings are near the player.
• If they are close to the player, do a point in AABB test to determine if the camera or player is in the building.
• If the player is in the building, check to see if any of it's portals are visible.
• If they are, extract the frustum planes from the portal(s) and cull the terrain geometry and objects to that portal.
  
• If point in AABB test determines that the camera/player is not in the building, then you have a bit more work to do.
• First test if any buildings are in the frustum.
• If they are, test if any of their portals are in the frustum.
• If they are, render the geometry in the building using the portal as the frustum cull.
• If by chance you have two windows with one leading to the outside, this will still work because eventually the portal leads back out of the building. This will enable you to see objects in the building, and also see the window on the other side that allows you to see the terrain through it.
• After you have rendered the buildings, it is time to render the terrain.
• Render the terrain using your quadtree system as well as any objects on the terrain.

This method will work well because:

• By drawing the buildings first you are covering up a lot of pixels on the screen and in the zbuffer. Since those buildings will most likely have a zbuffer value less than most of your terrain, you will speed up the final terrain rendering a lot.
• Because you can now render buildings with windows both into and out of the building this creates amazing displays where you can see through the building into a room that may in turn have windows leading outside, or doors that will render portions of the inside. When done right, this would look simply amazing.
• Because you know that the terrain will use a quad-tree and the indoor scenes will use a portal cull system, it is easy to switch between the two using recursive render calls to render the objects.
• The rendering method or scene method is a member of the object and therefore there is no way to get them confused.
• LOD is a moot point in indoor scenes unless you are trying to model something like a huge factory shop floor with vast expanses of open space. Small rooms such as in a castle or building should be rendered at full detail at all times since the objects will be probably with 200 to 500 units from the camera at all times.
• Since the quad tree system is a part of the terrain rendering, when you recursively call the terrain render code to render according to portals, the quad tree system will automatically be used. So you are rendering via a portal and you are still using the quadtree system. This will cull away thousands and thousands of triangles.

Thanks alot for the response Bubba, really lets me know that this is possible..

Approx time to implement quad trees, portal culling, and BSP: a year? :"D

I can see it now, the king peers out of his huge castle window, off to the horizon, you see a vast army approaching..

Another thing I want to be able to do is destroy buildings, apply damage in game, etc etc.. I want the enemy to be able to destroy the castle theyre sieging, not just take it.

Well you will have to make a decision there. Do you want to use varying models to show damage, decal textures, a combo of both, or do you want real-time model decimation?

For an extremely good example of real-time model decimation check out these games:

• Black and White 1 by Lionhead studios. Just take rock or object and smash the village. Very nice.
  
• Need for Speed: High Stakes and Porsche Unleashed. Real time damage to car models representing actual collision points...albeit somewhat toned down from real life.
  
• Mafia. Real time deformation of car models as it relates to damage and collision points.
  Excellent. You can drop the car off a bridge and provided the driver survives, you will see the end result as a messed up car...that may be driveable or may not.
  
• GTR. This racing sim will deform your car into an absolute wreck and it looks real and is very believable. Front ends can dent in, doors can dent in and out, and nearly every aspect of the car model can and is deformed at some point in time. Excellent.

For model-based constant damage effects check out:

• Grand Theft Auto 3, Vice City, and San Andreas. These all have damage models that represent varying degrees of damage. Even though it's not real time mesh deformation, it still damages the area that gets hit, even if it does get a bit repetitive seeing the same door with the same type of dent in it.
• Midtown Madness 1 and 2. Again, approximated damage models with a certain degree of realism.
• IL-2 Sturmovik/AEP/Pacfic Fighters version 4.03 and up. This has some of the best damage modelling for aircraft I've seen since Jane's WW2 fighters. Wings rip off, stabilizers get holes in them as well as the wings, rudder, etc, etc. Sometimes you can see through the wing to the ground as well as the fuesalage. Cockpit instruments get damaged and cracked, bullet holes pop up in the dash, and the cockpit window can get bullet holes and oil all over it. Smoke can pour out of nearly every orifice of the plane. Excellent damage modelling and excellent performance changes to the flight model based on the damage. There isn't any real-time model deformation but there are so many pieces of the craft that can come off, it is extremely realistic and believable.
• Combat Flight Simulator 1,2 and 3. Excellent damage modelling as it pertains to WW2 aircraft. Not as good as IL2/PF, but still very good.
• Janes WW2 Fighters. Probably one of the first people to get it right in a combat sim. Excellent damage effects, albeit a bit repetitive after a couple thousand hours in the sim.
  Lots of damage effects here and excellent crash and ground collision sequences. Excellent.
• Flight Unlimited 1 and 2. Especially 2. Nearly every piece of the aircraft could fall off or be ripped off and so effect performance and handling as well. Early sim, but extremely good damage modelling and also...a side note....some of the best terrain technology ever created.
• Papyrus NASCAR racing - all versions. The damage here is constant but is related to what you hit and how hard you hit it. Hoods fly off, front ends fly off, etc, etc. Very good for a racing sim. EA sports tries to do the same, but the end result is not as good as Papy.
• Demolition Derby 1 and 2. Constant damage modelling using textures and model changes or model mesh patches, but so many things to damage it's almost unbelievable.

For a great example of real time warfare as it relates to castle sieges I invite you to check out these engines:

• Medieval: Total War and Viking expansion pack.
• Rome: Total War and its new expansion pack.

No one has done it better than these two games as of yet. You can literally have thousands of troops on screen at a time, and in Rome they are all pure 3D. In Medieval they are done using billboards, but still look very good because of the many angles they have pre-rendered for the images. Both extremely good, extremely addicting, and really your jaw will drop when you hear the marching music and then watch 10000 guys battle 10000 other guys. One of my best gaming experiences ever.

Check out some other engines for very good terrain rendering:

• Far Cry. Nuff said. Bar none the best terrain ever seen in a shooter. Makes Unreal look like child's play.
• Joint Operations: Typhoon Rising and Escalation expansion pack. Very good visiblity ranges, awesome vegetation and trees - excellent frame rates. Excellent in all aspects if you ask me. Claim to be able to render 1/4 mile in all directions. Have not verified this, but I do know that I can see people well over 1500m in my sniper scope depending on fog settings. That's pretty damn far.
• Microsoft Flight Simulator 2004. No one, and I mean no one can do terrain like Microsoft.
  Bar none their terrain stretches to the horizon in all directions regardless of altitude. Excellent terrrain rendering. Check out CFS2 and CFS3 for renders using their FS2000 engine. The new 2004 engine is excellent but takes a hefty video card. Clouds are some of the best I've ever seen in any game and are rendered using 10 to 400 billboards per cloud. Close clouds are rendered as volume textures. For more information you can consult the web page of the guy who developed the cloud system. http://research.microsoft.com/~hoppe/. You can also see this guy helped with the terrain in FS9 based on his home page. Very good articles, all of them.
• Microsoft Train Simulator. Obviously since it uses the self-same FS2K engine. Good terrain, good visuals, great framerate - nuff said.

Good indoor renderers:

• Doom 3. Of course. Uses portal culling system.
• Half Life 2. Again a no-brainer. I think it still uses BSPs to great extent.
• Joint Operations: Typhoon Rising and Escalation. Excellent indoor to outdoor transitions with no framerate issues.
• Delta Force series - again even with early voxels, good indoor to outdoor transitions with insane visibility ranges.

Another game to check out which has some impressive indoor to outdoor effects is Full Spectrum Warrior. Excellent game and excellent visual effects.

As you can see I play a lot of games. It really helps to know what you are aiming for...what better way to find out than to play games and find out what you like and don't like.
Think of it as 'research'.

Also if you can get these games to run, they have some of the best sprite-based damage I've ever come across. These were done by Origin and unfortunately EA has pulled the plug on Origin. Crusader is one game begging for an awesome kick ass 3D update.

• Crusader: No Remorse
• Crusader: No Regret.

Sprite based damage modelling
These games simply just rock. You can blow up nearly everything on the screen, set dudes on fire, freeze em and shatter em with a shot, vaporize them into a pile of salt, or just gun em down mercilessly. Two wild rides that I'll not soon forget. The best damn games ever made and as such have been in the PC Gamer Hall of Fame for a long time.

Tile based damage modelling
Also Microprose's XCOM had very good damage modelling based on tiles. The newer XCOM: Apocalypse also has very good damage modelling with tiles from upper levels being able to smash down into and possibly also cause collapse to tiles on lower levels. It's a lot of fun to shoot some big tower at the base and watch the damn thing crumble onto some alien scum.

There are others out there that have real-time terrain deformation and a first person shooter that does constant model deformation. One that comes to mind is Red Faction. Solved the game on the XBOX so didn't get it for the PC. Good damage effects.

I'll stick this in another post because the first one was so long.

A simple way to do damage to a model is find out where the model is hit and the blast radius for the resulting explosion or damage area.

Then you can quickly compute which vertices fall into that area by using your cull tests and using the sphere as the cull volume. To prevent from having circular blast patterns at all times, use a random amount based on distance from center of hit and deform if the number is greater than or less than some value.

Find the points in the area and then make tri's out of those points in some type of orderly fashion. This is usually not too difficult. Now just fire off your particle system engine by giving the particles a starting velocity and velocity vector. Instead of using particle graphics you use the triangles as the particles and you can flip, rotate, or do whatever you want to the tri's to make it look real. As gravity acts on the tri's this will cause them to fall towards the earth. If you wish to do some bouncing simply do a bilinear interpolation with the ground to find the height at the point of impact. Calculate the physics reponse for velocity and then multiply the directional vector by the normal of the triangle you hit. The physics engine then will act on the object and eventually the energy will reach 0 and thus the object will stop on the ground somewhere. You can combine this with some razzle dazzle particle effects and some cool explosion billboards and you have yourself some very believable explosion effects.

If you want more info, I will explain in great detail how to go about doing this and how to structure your models to get the job done.

But this is going to be CPU intensive so make sure it's worth it. Sometimes the razzle dazzle is so fast it's not noticed and sometimes it's just not worth the bother when a normal explosion billboard with some particle effects will do the trick.

In DX real-time deformation is hampered by the fact that this requires dynamic vertex buffers and real-time locking and unlocking of vertex buffers which hinders performance greatly.

Real time terrain deformation is a simple matter of finding the blast radius and force and then displacing the Y component of the vertices based on distance from center with some random perturbation to make it look rugged. No new vertices need to be added. Now if several huge explosions hit the same area, you may want to add some vertices or a terrain patch so that you don't get extremely spikey looking terrain areas. A very quick way to do this if you are computing vertices on the fly is to make a copy of the heightmap and then deform it. That way whenever that section of terrain is rendered, the deformation is already encoded into the height. This is a major speed up.

Jee Bubba you really like to write..

I like it when you do this because I can refer back to this thread for another 6 months or so lol..

Right now I'm getting familiar with boost shared/weak pointers.. I'm pretty sure that is the only way I can get my resource manager to not break the game if a resource is released while it is being used somewhere else.

BTW, an RTS is not exactly what I have in mind..

I'm talking more on the lines of, MMO.

*audience goes quiet*