Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualNorman Barrows

Posted 18 April 2013 - 11:40 AM

get out your flamethrowers!

relational databases implemented as static arrays.

one list of vertices/meshes
one list of object types
one list of active objects

an object struct has an active field to indicate whether its in use and should be drawn etc.
it also has a type field, which is the index of its type in the list of object types.

the object types struct has a meshID field , which is its index into the mesh database.

to draw:
for a=0; a<maxobjs; a++
if (objj[a].active)
{
t=objj[a]type
m=objtype[t].meshID
drawmesh(obj[a].x,obj[a].y,[obj[a].z,meshID);
}

objrecs carry target specific info like active, location, orientation, type, and damage.

objtype recs carry type info like meshID, hp, maxspeed, turnrate, etc.

for static objtypes, it may just be name, meshID, and hp.

but this will be the fastest data structure.

possible speedups include putting more info in the objrec to reduce some dereferenced addressing, but its not worth it.
if the target list is large, it can be ordered on x,y,z and indexed on x,y, or z to speed up searches. i use that method on a list of 18,000 huts to draw. but i don't even need it for drawing, i use it for collision checks while drawing: "i'm drawing a plant. is there a hut in the way? ok, no plant then." the list is sorted on x, then y, then z. then the list is indexed on x lets say. the index has the offset of the first object with that x, and the number of objects with that x. when you need to know if there's an object at some x,y,z, you lookup the start offset in the index, then loop thru the list from there for the number of objects with that x. since its ordered, you can bail as soon as x gets too big, or y gets too big for a given x, or z gets too big for a given x and y.
but that speedup is primarily for collision checks, not drawing. for drawing, looping thru the list with "if active, draw" is plenty fast. an even faster speedup for collision checks is to create a collision map from the list of objects. a simple monochrome bitmap with a 1 where there's an object, and a zero where there isn't. or a 2d array of unsigned char, unsigned short, or unsigned int, that uses obj# (index in the obj database)) instead of 1 to indicate terrain in way. that way, you know what you hit. for each object in your database, you fill in the collision map with its id#. and use something like -1 to indicate open space (no collision). when its time to check for collision:
obj_collided_with=collisionmap[x][z];
if (obj_collided_with != -1) handle_collision()
hard to get faster that that.

used to lookup if object has been drawn or needs drawing or removing.


sounds like you may have less than most efficient flow control, as well as data structures.

i can't think of any reason why one would need to lookup if something had been drawn yet. this is something that your flow control code should know at all times, as its what controls the drawing of objects.

your basic drawing routine should be something like:
for (a=0; a<maxobjs; a++)
{
if (!obj[a].active) continue;
if (far_away(a)) continue;
if (frustum_cull(a)) continue;
drawit(a);
}

#1Norman Barrows

Posted 18 April 2013 - 11:27 AM

get out your flamethrowers!

 

relational databases implemented as static arrays.

 

one list of vertices/meshes

one list of object types

one list of active objects

 

an object struct has an active field to indicate whether its in use and should be drawn etc.

it also has a type field, which is the index of its type in the list of object types.

 

the object types struct has a meshID field , which is its index into the mesh database.

 

to draw:

for a=0; a<maxobjs; a++

if (objj[a].active)

   {

   t=objj[a]type

  m=objtype[t].meshID

  drawmesh(obj[a].x,obj[a].y,[obj[a].z,meshID);

   }

 

objrecs carry target specific info like active, location, orientation, type, and damage.

 

objtype recs carry type info like meshID, hp, maxspeed, turnrate, etc.

 

for static objtypes, it may just be name, meshID, and hp.

 

but this will be the fastest data structure.

 

possible speedups include putting more info in the objrec to reduce some dereferenced addressing, but its not worth it.

if the target list is large, it can be ordered on x,y,z and indexed on x,y, or z to speed up searches. i use that method on a list of 18,000 huts to draw. but i don't even need it for drawing, i use it for collision checks while drawing: "i'm drawing a plant. is there a hut in the way? ok, no plant then." the list is sorted on x, then y, then z. then the list is indexed on x lets say. the index has the offset of the first object with that x, and the number of objects with that x.   when you need to know if there's an object at some x,y,z, you lookup the start offset in the index, then loop thru the list from there for the number of objects with that x. since its ordered, you can bail as soon as x gets too big, or y gets too big for a given x, or z gets too big for a given x and y.

but that speedup is primarily for collision checks, not drawing. for drawing, looping thru the list with "if active, draw" is plenty fast. an even faster speedup for collision checks is to create a collision map from the list of objects. a simple monochrome bitmap with a 1 where there's an object, and a zero where there isn't. or a 2d array of unsigned char, unsigned short, or unsigned int, that uses obj# (index in the obj database)) instead of 1 to indicate terrain in way. that way, you know what you hit. for each object in your database, you fill in the collision map with its id#. and use something like -1 to indicate open space (no collision).  when its time to check for collision:  

obj_collided_with=collisionmap[x][z];

if (obj_collided_with != -1)  handle_collision()

hard to get faster that that.


PARTNERS