Tag Archive for 'opengta2'

OpenGBH octree use for maps

An idea was suggested to me – using octree for storing map data in OpenGBH. It seems like quite an interesting idea, since OpenGBH maps are usually full of nil space (blocks not filled in any way), they are not limited in size (so they must be stored in some sort of chunks).

To be more exact, map would be stored as quadtree and octree. The division into quadtree is for dividing city into major blocks, each of the blocks containing a whole map portion. Division into octree divides those portions into sets of blocks, and finally into separate distinct blocks. But not ending there division can go further and create ability to subdivide map blocks into smaller ones for more complex architecture and level geometry.

Quadtree divison starts from the root node – this node (like all others) is rectangular in size, and it’s big enough to fit the entire map. For example for GTA2 city it would be a 256x256x32 node (assuming city can be up to 32 blocks high – which is an incredibly high limit actually).

The root node divides into smaller ones, all of which have the same height (all dimensions are in game “blocks”):


After this division into octree starts – every node divides into 8 other nodes, until it reaches size of a single block:


After this subdivision of each separate block starts – it’s possible to divide blocks into very small pieces, there is a lower limit though (about 0.03% of size of a whole block). Actually this works the same way for larger blocks – it’s possible to define one big 4x4x4 block.

This should make uncompressed map take less space in RAM than an equivalent 3D array (possibly division schematic should be revised, maybe there’s a more optimal way to divide map.. not sure right now though).

This should allow the whole level to be built in a very flexible way. Each block (or part of a block) can be one of the predefined slope geometries – meaning you can make some unusual constructions never possible in GTA2.

OpenGBH car physics

I’ve started working on car physics. There are some reasons why I don’t want to take something like Bullet physics library – mostly for academic reasons (car physics are quite simple), plus I want something that I can optimize for multiplayer later on.

Right now the car collision is checked as polygon versus triangle for walls, and rays versus triangles to compute wheels (just one wheel actually – figured out OpenGBH car physics should stay arcade-styled, plus easier this way).

Single wheel means there’s just a single point where vehicle touches ground (in its center of mass). There’s no rendering for cars (or anything else), so it just looks like this:

I’m thinking the collision for car versus car will be based on axis-aligned bounding box versus arbitrarily aligned box test. So collisions on various axes and between different objects are quite different – most likely I will add shock propagation for collision solver too, since I predict there might be situations where people will want to take physics to the extreme. Better to just let them do that!

OpenGBH engine layout

This post describes general layout of how OpenGBH engine is structured, and what two main threads do.

Simulation thread runs the simulation loop with a fixed timestep, resulting in a 30 FPS simulation. This includes processing pedestrians, game logic, car physics, and manages loading maps. All the game state is stored in a game frame, which looks like this right now:

struct gbh_frame
	//Pedestrian pool
	gbh_memory_pool* ped_pool;
	//Car pool
	gbh_memory_pool* car_pool;
	//Client pool
	gbh_memory_pool* client_pool;
	//Map lookup table
	rmp_cityscape* map_lookup[16][16];

	//Global pedestrian counter
	pedID ped_counter;

	//Current frame number
	uint sequence;
	//Current frame time
	float64 time;

	//Is this frame reliable?
	bool reliable_frame;
	//Is this frame extrapolated?
	bool extrapolated_frame;

	//Pointer to previous frame, if such exists (used for delta-comparsion)
	gbh_frame* previous_frame;

Each frame represents game state at certain point of time – simulation thread preserves several of these states (although not used in singleplayer mode, in multiplayer mode this is required for plenty of reasons).

Rendering thread is a separate application, it’s statically linked with the simulation part though. There can be different rendering applications, they would all need to call gbh_frame* frame_render() routine that copies current frame from simulation thread to the rendering thread.

The new copied frame has no connections to the server thread, apart from the map data (which is shared, and protected with mutexes and reference counting). All the other data can be changed by client, like for example for interpolation (to increase percieved FPS from 30 to rendering FPS).

OpenGBH script updates

I’ve been working on the OpenGBH engine again. This is the fifth iteration of the engine I think, this time I’m starting with building engine that would have scalability and scripting from the start. It already makes use of two CPU cores for actual game simulation and rendering.

Each of the two threads normally running (there’s just two threads you can run scripts in – although there might be some special case when it might be possible to run certain script in thread other than the two main ones…) has own Lua script state.

These states are not connected in any way, they even allocate memory from different heaps. The simulation thread runs all the scripts which alter game logic – and actually 90% of game logic is driven by scripts. The engine only provides general API, and implements many time-critical routines in C.

The client thread (rendering thread) scripts only draw HUD, and process some keyboard input, do all the GUI/menu stuff. They are only for visualization of what happens in the server-side script.

The game can be entirely changed by the script – as was said before, 90% of the logic is defined by just the scripts. From my experience, this is a much better alternative due to scripting flexibility.

OpenGBH scripting update

I’ve created special type for pedestrians – GBHPed, which is now treated by lua as a new datatype (works through userdata). The problem that rises here is that it creates a memory allocation each time it allocates a new pedestrian – and lifetime of these allocations are quite low, creating a huge amount of fragmentation.

I’m just going to solve this by using a simple allocator which allocates fixed-size blocks from a fixed pre-allocated memory area. This should remove any fragmentation that occurs, and the queue is emptied every frame by the lua garbage collector.

My current idea for the allocator itself – just a queue of fixed-size blocks. First byte in the block shows whether the block is free or not, and the allocator stores a pointer to the next element in the queue. When you need to allocate a new block, you move to the next element in the queue, at least until you find a free one. This should serve as a psuedo-code:

char* fastmem_48;
char* fastmem_48_current_ptr;
char* fastmem_48_last_ptr;
void memory_initialize_fastmem_48(int max_elements)
	fastmem_48 = malloc(52*max_elements);
	fastmem_48_current_ptr = fastmem_48;
	fastmem_48_last_ptr = fastmem_48+52*max_elements;

void* memory_fastmem48_alloc()
	while (*fastmem_48_current_ptr == 1)
		fastmem_48_current_ptr += 52;
		if (fastmem_48_current_ptr == fastmem_48_last_ptr)
			fastmem_48_current_ptr = fastmem_48;
	*fastmem_48_current_ptr = 1;
	fastmem_48_current_ptr += 52;
	return (void*)(fastmem_48_current_ptr-48);

void memory_fastmem48_dealloc(void* ptr)
	*((char*)ptr-4) = 0;

That probably has a lot of bugs somewhere, but should give a rough idea. Actually I think perfomance-wise it makes sense to stuff all allocations under 124 bytes into this kind of an allocator, even though it’s a memory waste. Some extra bytes come from padding the stuff to right boundary.

OpenGBH scripting change

From a discussion with people at #lua @ irc.freenode.org I’ve decided to change how the scripts work with multithreading, and how the multithreading generally works. Now each thread will get an own dedicated Lua state, and therefore the scripts are very roughly split into these categories:

  1. Server scripts/gameplay scripts (they run gamemode)
  2. Pedestrian physics override scripts
  3. Vehicle physics override scripts
  4. Misc entity override scripts
  5. Clientside scripts

Each of those can only communicate with the game in three ways: either read data from the current frame, write changes to currently simulated frame, or call an inter-thread communication routine. The last is more of a hack, and it’s not recomended to use it.

The AI will be based on the Lua coroutines – each coroutine specifies a continious sequence of commands for the pedestrian. Whenever the current command interrupts due to some external influence, it returns, and it’s possible to check the return code to determine what exactly interrupted it.

Sorry for no posts, but this week was really busy with all kinds of stuff. I’m still working on the XV-102 estimation, and wrote some software, more on it later. Random picture from the program:

OpenGBH lua update

I’ve worked a bit more on the lua side of the game (which means I didn’t actually have time to really work on it – but I’ve decided to use time when I lack enough motivation to work on very simple tasks, thankfully there’s plenty so far).

There was one curious change you might be interested in. Here’s a problem for you: how do you store objects which can be accessed by Lua scripts, but aren’t present anywhere in Lua. You can’t just use them, they would be picked up by Lua garbage collector at some point.

Easy solution: store all references in a table which lies on stack. The objects on stack aren’t garbage-collected, so you can use this to your advantage. The program can go like this:

//Invisible table for storing all the references to internal game objects

... game loop ...

//Delete the internal reference table

And when you want to use the table (make sure you know what you’re doing):

//Get value from internal reference table
//Alternatively you can use this, but I prefer previous line,
//cause it triggers an error if you mess up stack somewhere
//Get temporary ped table
//Create it if it doesn't exist
if (!lua_istable(sv_lua_state,-1))
	//Pop the nil value left over from "getfield"
	//Create the table
	//Copy the table on stack, cause "setfield"
	//will remove it from stack

//Read Position field
if (!script_checkvec3(sv_lua_state,-1))
	//Pop something that isn't position vector
	//Create a position vector for later use
	//Pop "Position" vector, we dont need it now

//Set temporary ped data

//Get ped process function
if (lua_isfunction(sv_lua_state,-1))
	//Push temporary ped data into function
	//A copy remains on stack under the function
	//Call the function with 1 argument and no results
	//Both function and its single argument were popped by lua_call
	//We can now set the copy of _temporary_ped we havecs
	//Pop something that isn't a function
//Pop "_temporary_ped"

Another problem – call a C function in a protected envrionment, while retaining stack (or at least passing some parameters). “Correct” way is to use lua_cpcall, but that only allows you to transmit a single pointer. You can use lua_pushcfunction and lua_pcall instead – that way allows you to transmit any amount of parameters into and out of the function.

OpenGBH ped scripting update

I’ve been working on the OpenGBH scripting – I have wrote a new lua vector implementation (now it uses metatables and userdata, and behaves like a real data type, and not a table). I’ve also reduced the amount of memory allocations in each frame to zero (before that the game would slowly crawl down to low speed due to high amounts of data allocations).

Data allocations were a result of vectors being passed around from pedestrian solver into script. I’ve removed that, and everything runs lighting fast now. Memory allocations are much slower than I expected before.. I knew they were slow, but not this slow!

Not so much peds should be handled by the script though. The pedestrian AI is handled by the game engine – the script is only required if you want to override pedestrian behaviour, physics, etc.

Oh, and rendering is very nicely separated from the simulation… I will tell you how in one of the next posts. No pictures today either, sorry.