Jump to content
  • Advertisement
Sign in to follow this  
coderWalker

[ ] Chunk management [ ]

This topic is 2701 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

My game uses a textured Voxel engine.
The world is made of Chunks.
Each chunk is 16x16x16 blocks.

Just so you can get a feel for what I'm talking about:
bug5.png

I am now trying to utilize 2 threads to run the game. I am using the boost_thread library on Linux.

I have been trying to get this to work for the last 5 hours (yes I'm persistent)
I have been over and over the code and still can't locate the problem.

Chunk Management--
I have a class for the world called world with the instance used in the game being world0.
In that class I have 2 3d arrays which store pointers to chunks and bool exists.
chunk* chunks[7][7][7]; <- pointers to the chunks
bool chunkExists[7][7][7]; <- Weither a chunk has been created or loaded at that point.

world::world(int pName)
{
drawSkyBox=true;
name = pName;
time=1.000f;
timeAdd=0.000f;
//Make Chunks
//xChunks=CLIPDIST;
//yChunks=CLIPDIST;
//xOffset=((CLIPDIST-1)/2)+1;
//yOffset=((CLIPDIST-1)/2)+1;

//Set all the chunks to nonexisting
for (int a=0;a<CLIPDIST;a++)
{
for (int b=0;b<CLIPDIST;b++)
{
for (int c=0;c<CLIPDIST;c++)
{
chunkExists[a][c]=false;
}
}
}
init=true;
wait=WAITTIME;
running=false;

}


When the map is created it creates a chunk for each position before the game starts.
Then it creates a thread (~Thread 2) that will watch the chunks and create a new one as needed.
It basically for now loops checking the map and if it sees an exists==false it will create a new chunk.
So that when the map scrolls the new chunk will already be there.
It only exists this loop when the game ends.
void world::startThread()
{
//Create the Load chunk Thread
tMapLoading = boost::thread(boost::bind(&world::checkChunks, this));
running = true;
}
void world::checkChunks()
{

bool changed=false;
for (signed int iChunkY=0;iChunkY<CLIPDIST;iChunkY++)
{
for (signed int iChunkX=0;iChunkX<CLIPDIST;iChunkX++)
{
for (signed int iChunkZ=0;iChunkZ<CLIPDIST;iChunkZ++)
{
if (chunkExists[iChunkX][iChunkY][iChunkZ]==false)
{
signed int xCur=xOffset+iChunkX-HALFCLIPDIST;
signed int yCur=yOffset+iChunkY-HALFCLIPDIST;
signed int zCur=zOffset+iChunkZ-HALFCLIPDIST;
Chunk[iChunkX][iChunkY][iChunkZ] = new chunk(xCur,yCur,zCur);
chunkExists[iChunkX][iChunkY][iChunkZ]=true;
//cout << xCur << "\n" << yCur << "\n";
Writer->readChunk(xCur,yCur,zCur,iChunkX,iChunkY,iChunkZ);
//Writer->writeChunk(xCur,yCur,zCur,iChunkX,iChunkY,iChunkZ);
changed=true;
}
}
}
}
if (changed)
{
bufferInitAll();
cout << "New Chunks Created by Init\n";
}

while (running)
{
bool changed=false;
for (signed int iChunkY=0;iChunkY<CLIPDIST;iChunkY++)
{
for (signed int iChunkX=0;iChunkX<CLIPDIST;iChunkX++)
{
for (signed int iChunkZ=0;iChunkZ<CLIPDIST;iChunkZ++)
{
if (chunkExists[iChunkX][iChunkY][iChunkZ]==false)
{
signed int xCur=xOffset+iChunkX-HALFCLIPDIST;
signed int yCur=yOffset+iChunkY-HALFCLIPDIST;
signed int zCur=zOffset+iChunkZ-HALFCLIPDIST;
Chunk[iChunkX][iChunkY][iChunkZ] = new chunk(xCur,yCur,zCur);
chunkExists[iChunkX][iChunkY][iChunkZ]=true;
//cout << xCur << "\n" << yCur << "\n";
Writer->readChunk(xCur,yCur,zCur,iChunkX,iChunkY,iChunkZ);
//Writer->writeChunk(xCur,yCur,zCur,iChunkX,iChunkY,iChunkZ);
changed=true;
}
}
}
}
if (changed)
{
bufferInitAll();
cout << "-------------------------------------------------! New Chunks added by thread 2!-------------------------------------------------\n";
}
}
}


Map scrolling--
When the map scrolls it moves the pointers and sets the ones that need a new chunk to false in the chunkExists array.
This is so that ~thread 2 will see the false and create a new chunk in that position.

Player moves right on map (5 more simular to this exist):
void world::xOffsetAdd()
{
printf("Map->xOffset+=1\n");
xOffset+=1;
////Save Shifted
int x = 0;
for (int y=0;y<CLIPDIST;y++)
{
for (int z=0;z<CLIPDIST;z++)
{
if (chunkExists[x][y][z]==true)
{
Writer->writeChunk(Chunk[x][y][z]->location.x,Chunk[x][y][z]->location.y,Chunk[x][y][z]->location.z,x,y,z);
delete Chunk[x][y][z];
chunkExists[x][y][z]=false;
}
}
}
////Shift Map -x
for (int x=0;x<CLIPDIST-1;x++)
{
for (int y=0;y<CLIPDIST;y++)
{
for (int z=0;z<CLIPDIST;z++)
{

Chunk[x][y][z]=Chunk[x+1][y][z];
chunkExists[x][y][z]=true;
}
}
}
////Delete Old
x = CLIPDIST-1;
for (int y=0;y<CLIPDIST;y++)
{
for (int z=0;z<CLIPDIST;z++)
{
chunkExists[x][y][z]=false;
}
}
/*
////Delete Old
x = CLIPDIST-1;
for (int y=0;y<CLIPDIST;y++)
{
for (int z=0;z<CLIPDIST;z++)
{
signed int xCur=xOffset+x-HALFCLIPDIST;
signed int yCur=yOffset+y-HALFCLIPDIST;
signed int zCur=zOffset+z-HALFCLIPDIST;
Chunk[x][y][z] = new chunk(xCur,yCur,zCur);
chunkExists[x][y][z]=true;
Writer->readChunk(xCur,yCur,zCur,x,y,z);
}
}
//Fix Buffers
x = CLIPDIST-1;
for (int y=0;y<CLIPDIST;y++)
{
for (int z=0;z<CLIPDIST;z++)
{
Chunk[x][y][z]->bufferInit();
Chunk[x-1][y][z]->bufferInit();
}
}
*/
}


Map drawing--
The map only draws from 2 to 4 inclusive in every direction by the means of for loops.
When drawing the chunks it also first checks if they exist if they dont it doesnt draw them.

oid world::draw()
{
wait--;
glPushMatrix();
glTranslatef(-HALFCLIPDIST*16,-HALFCLIPDIST*16,-HALFCLIPDIST*16);
if (drawSkyBox)
{
drawSkydome();
}
//checkChunks();
//Draw Opaque
for (int iChunkY=2;iChunkY<CLIPDIST-2;iChunkY++)
{
for (int iChunkX=2;iChunkX<CLIPDIST-2;iChunkX++)
{
for (int iChunkZ=2;iChunkZ<CLIPDIST-2;iChunkZ++)
{
/*if (!chunkExists[xCur][yCur])
{
Chunk[xCur][yCur] = new chunk();
chunkExists[xCur][yCur]=true;s
printf("/!\\ MISSING CHUNK (%d,%d)\n",xOffset,yOffset);
}
else*/
{

if (chunkVisible(iChunkX,iChunkY,iChunkZ)==true && chunkExists[iChunkX][iChunkY][iChunkZ]==true)
{
Chunk[iChunkX][iChunkY][iChunkZ]->drawOpaque(iChunkX*16,iChunkY*16,iChunkZ*16); //iChunkY-0
}
if (wait==0 && chunkExists[iChunkX][iChunkY][iChunkZ]==true)
{
Chunk[iChunkX][iChunkY][iChunkZ]->update();
}
}
}
}
}
//Draw Transparent
for (int iChunkY=0;iChunkY<CLIPDIST;iChunkY++)
{
for (int iChunkX=0;iChunkX<CLIPDIST;iChunkX++)
{
for (int iChunkZ=0;iChunkZ<CLIPDIST;iChunkZ++)
{
if (chunkVisible(iChunkX,iChunkY,iChunkZ)==true && chunkExists[iChunkX][iChunkY][iChunkZ]==true)
{
Chunk[iChunkX][iChunkY][iChunkZ]->drawTransparent(iChunkX*16,iChunkY*16,iChunkZ*16); //iChunkY-0
}
}
}
}
/*
//Draw Translucent
for (int iChunkY=0;iChunkY<CLIPDIST;iChunkY++)
{
for (int iChunkX=0;iChunkX<CLIPDIST;iChunkX++)
{
for (int iChunkZ=0;iChunkZ<CLIPDIST;iChunkZ++)
{
if (chunkVisible(iChunkX,iChunkY,iChunkZ)==true)
{
Chunk[iChunkX][iChunkY][iChunkZ]->drawTranslucent(iChunkX*16,iChunkY*16,iChunkZ*16); //iChunkY-0
}
}
}
}*/
glPopMatrix();
if (wait==0)
{
wait=WAITTIME;
time+=timeAdd;
if (time>=1.0f || time <= 0.0f)
{
timeAdd=-timeAdd;
}
GLfloat global_ambient[] = { time,time,time, 1.0f };
glLightModelfv(GL_LIGHT_MODEL_AMBIENT, global_ambient);
}
}


For some reason my game just crashes at random and i don't know why.
It's throwing a segmentation fault.
I think the game is trying to access a chunk that doesn't exist.
I just can't find out where.
Anyone have any ideas?
Am I using threads properly?
I know this is not a simple problem but, someone please spot the problem.
Thanks, because today has been a really upsetting day.

Share this post


Link to post
Share on other sites
Advertisement

Well the obvious question would be: did you try running your program with a debugger?


Yes, thats how I know it's a segmentation faught.

I really want to know am I createing the thread correctly and am i planning on using it correctly?

Share this post


Link to post
Share on other sites

[quote name='SiCrane' timestamp='1298083947' post='4776190']
Well the obvious question would be: did you try running your program with a debugger?


Yes, thats how I know it's a segmentation faught.

I really want to know am I createing the thread correctly and am i planning on using it correctly?
[/quote]
The big issue that comes right to the top is that it doesn't look like you are synchronizing anything. You need mutex/semaphores/condition variables (all in the boost::thread library) to "lock" any data that is shared. Your thread can't be allowed to write to any piece of data that may be read inside another thread.

Using bools and volatile is not a substitute for proper synchronization. While, at first glance your bools may look to be properly flagging chunks loaded or not, they are not atomic operations, and may arrive after or before your data is actually ready.

If done improperly, this will "serialize" your parallel threads, resulting in a reduction in performance from the single threaded version. So you really need to separate the logic for loading from any of the logic for moving around the map.
I'll reduce this to a 1d case that you can expand to the 3d case.

If you were on a line at 2, and could only see 2 blocks on either side. You'd see 1 and 3. Lets say we then move to 3. Your memory looks like this

0 [1,2,3] 4 5 6
^

So, we then know we need chunk 4, and maybe 5. so you do something like:

void queue_load()
{
boost::scoped_lock( loader_mutex )
loader_queue.push_back( 4 );
loader_queue.push_back( 5 );
loader_cv.signal_one();
}

void loader_thread()
{
while( running )
{
chunk_id newId;

// only lock to deque an item
{
boost::scoped_lock( loader_mutex );
if( !loader_queue.empty() )
{
newId = loader_queue.back();
loader_queue.pop_back();
}
else
{
loader_cv.wait( loader_mutex );
continue;
}
}

// do load of newId now that the loader queue is unlocked
Chunk chunk = load( newId );

{
boost::scoped_lock( game_data_mutex );
copy_item_to_map( chunk, newId );
}
}
}

void game_loop( )
{
// do stuff that doesn't need the map

{
boost::scoped_lock( game_data_mutex );
// do stuff that needs the map
// display map?
}

// do other stuff that doesn't need the map
// maybe yield() to give up the remainder of your current timeslice to the loader thread
}


The result is that 4 and 5 are queued up on the other thread. The other thread is waiting on the condition variable, not using resources, untill signaled. Once signaled, it wakes up, and pops an item to load. It releases the mutex loads a copy of the data and then locks the game data so it can copy in the new block. The main loop just chugs along and locks before displaying the map, and unlocks after. That way the main thread will never be reading the map while the loader is copying in a new block.

Share this post


Link to post
Share on other sites
Thanks for the code.

The check chunk thread checks the whole map
The draw map only draws chunks atleast 2 from all edges.
Shouldn't the checkChunk thread have the data loaded in time?
for (signed int iChunkY=0;iChunkY<CLIPDIST;iChunkY++)
{
for (signed int iChunkX=0;iChunkX<CLIPDIST;iChunkX++)
{


for (signed int iChunkY=2;iChunkY<CLIPDIST-2;iChunkY++)
{
for (signed int iChunkX=2;iChunkX<CLIPDIST-2;iChunkX++)
{


Ignore that
A map shift while it's changing a chunk is possible.
I have some questions about the code.

Threads:
0-Main game thread
1-checkChunk thread

Can you explain what this line does and where game_data_mutex comes from?
boost::scoped_lock( game_data_mutex );

Where is this class defined ?
loader_queue.push_back( 4 );
loader_queue.push_back( 5 );
loader_cv.signal_one();

If I "pause" thread 0 while thread 1 is working then would it be any faster than the single threaded version?

Share this post


Link to post
Share on other sites

Can you explain what this line does and where game_data_mutex comes from?
boost::scoped_lock( game_data_mutex );
[/quote]
Sorry, i typed that all up too quick. They are just two boost::mutex that you define somewhere in code.


Where is this class defined ?
loader_queue.push_back( 4 );
[/quote]
Any old queue will work. std::deque or std::vector


loader_cv
[/quote]
Should be a boost::condition_variable


If I "pause" thread 0 while thread 1 is working then would it be any faster than the single threaded version?
[/quote]
No, it won't. Thats why I was trying to get at the idea of separating out the logic enough. Your loader thread has to be able to get data from the disk into unused areas of your map (or a holding queue of loaded data). It only has to lock the output queue when it adds data to it. Your main thread then only occasionally locks to check if there is new data from the loader thread. As long as neither thread holds onto their shared mutex for long, then they will run in parallel.

Share this post


Link to post
Share on other sites
I think the reason I am just not getting this is because I am biting off more than I can chew.

I mean I am just starting threads, and am now trying to implement mutex's threads and vectors.
All 3 I have never used before.

If I was to use the threads and just use the mutex locks and unlocks would that be sufficient for now?
I can always add on and make it more efficient later.

About the Mutex::lock();
Please verify I am understanding this correctly When a thread reaches this, it will pause all the other
threads until an unlock is hit at which the other threads will resume. It doen't actually lock out threads
does it?

I know this may seem basic to some people but this is new to me and the only way I learn is ask questions.
Thanks for the help!

Also how does scoped_lock work? There is no unlock command?

Share this post


Link to post
Share on other sites
I added "boost::mutex::scoped_lock lock(mMapLoading);" where the loader thread changes the map.
I also added "boost::mutex::scoped_lock lock(mMain); where the main thread access the map.
It still crashes?

Share this post


Link to post
Share on other sites

About the Mutex::lock();
Please verify I am understanding this correctly When a thread reaches this, it will pause all the other
threads until an unlock is hit at which the other threads will resume. It doen't actually lock out threads
does it?

No. It does not "pause all the other threads". It does in fact "lock out threads". When a thread hits a "lock" command on a mutex, it checks with the OS if the mutex is available and then locks it. When another thread tries to lock the same mutex, that thread is suspended until the mutex is unlocked. A mutex therefore keeps two threads from accessing a piece of shared data by locking out one thread while the other is using that data.

A condition variable lets you use a mutex to protect shared data but lets you choose when to wake and sleep one or more threads. In the standard producer-consumer problem, all the consumers sleep on a CV until the producer provides work to one of them. By signaling the CV, the producer can wake a single worker to process an item. So, the workers don't waste CPU if there isn't enough work to do.


Also how does scoped_lock work? There is no unlock command?
[/quote]
Is locks a mutex within the scope of the lock variable. Like any C++ object, it constructs where you create the variable and destructs when it falls out of scope. On construction it locks the mutex, and on destruction it unlocks it.

Share this post


Link to post
Share on other sites
I have been looking over meny tutorials and have tried to understand what they are explaining.
To my understanding:
More than 1 thread can never access the same resource.
Mutex's are used so that threads do not modify the same data somutaniously.
When a mutex::lock deconstructs it unlocks.
When a thread hits a mutex::lock...
if locked
it waits until it is unlocked
if unlocked
it lockes the mutex and continues executing.

I now understand what you were saying about the Queneing. To do threads effectively
they must share little of the same variables. In my case just 2 arrays (bool and chunk*)
are being accessed by the two threads. So there needs to be a middle ground.
Like so: (thread is hereby refered to as ~ )
~0 = Main ~
~1 = loader ~

creation:
~0 -> Create thread 1
~0 -> Continue game
~1 -> remain in loop awaiting work

loop:
~0 -> map scroll
~0 -> add work to ~1
loop while work
~1 ->perform work
~0->check on work

All this correct?

Are threads considered an advanced topic?

I have got meny programs and have wondered "Why is this not multithreaded!?" now I know. :P

I have added some condition variables but have commented them out because I want to atleast
get the threads working in parallel before sleeping and unsleeping them. However I know this is
required because now if someone has a Single core processor I am mostly killing 50% of thier
performance, while multicore users are gaing about 50% (less due to over head)

Mutex's
I have 3 commands that deal with modifying the Quene

//Called by Thread0 - Main
//Adds a new job to the Quene
void world::thread1add(int x, int y, int z)

//Called by Thread0 - Main
//Copies All the work from the Quene to appropriate places (i hope)
void world::thread1recieve()

//Called by Thread1 - Loader
//Thread1 loops here checking for new jobs
void world::thread1loop()

All three of these Lock the mMain mutex.
Meaning no 2 can happen concurrently.

Thread0 is the only one with access to:
Chunks[][][] and chunkExists[][][]
These are refrenced by about 16 functions and would be too much locking.

Both Threads have access to:
//Holds jobs
vertexChunk thread1Quene[thread1QueneLimit];
~0 adds jobs, while ~1 performs.

Now, hope this wasn't too much information. Want you to know I am not just
wasting your time and am trying my hardest to learn this, and also a little but about
how i *think it should work. My program still does not work.

Anyone spot any problems?

map.h snipplets:

//Threads
boost::thread tMapLoading;
boost::mutex mMapLoading;
boost::mutex mMain;
boost::condition_variable vMapLoading;
vertexChunk thread1Quene[thread1QueneLimit];

map.cpp snipplets:

world::world(int pName)
{
drawSkyBox=true;
name = pName;
time=1.000f;
timeAdd=0.000f;
//Make Chunks
//xChunks=CLIPDIST;
//yChunks=CLIPDIST;
//xOffset=((CLIPDIST-1)/2)+1;
//yOffset=((CLIPDIST-1)/2)+1;

//Set all the chunks to nonexisting
for (int a=0;a<CLIPDIST;a++)
{
for (int b=0;b<CLIPDIST;b++)
{
for (int c=0;c<CLIPDIST;c++)
{
chunkExists[a][c]=false;
}
}
}
init=true;
wait=WAITTIME;
running=false;
for(int a=0;a<thread1QueneLimit;a++)
{
thread1Quene[a].exists=false;
}
}

//Called by Thread0 - Main
void world::startThread()
{
//Create the Load chunk Thread
tMapLoading = boost::thread(boost::bind(&world::thread1loop, this));
//vMapLoading = boost::condition_variable;
//mMapLoading = boost::mutex
running = true;
}

//Called by Thread0 - Main
void world::thread1add(int x, int y, int z)
{
boost::mutex::scoped_lock( mMain );
for(int a=0;a<thread1QueneLimit;a++)
{
if (thread1Quene[a].exists==false)
{
thread1Quene[a].x = x;
thread1Quene[a].y = y;
thread1Quene[a].z = z;
thread1Quene[a].exists = true;
}
}
}
//Called by Thread0 - Main
void world::thread1recieve()
{
//boost::mutex::scoped_lock lock(mMain);
boost::mutex::scoped_lock lock(mMain);
//boost::scoped_lock( mMapLoading );
//loader_cv.wait( mMapLoading );
for(int a=0;a<thread1QueneLimit;a++)
{
if (thread1Quene[a].exists==true)
{
Chunk[thread1Quene[a].x][thread1Quene[a].y][thread1Quene[a].z] = thread1Quene[a].chk;
chunkExists[thread1Quene[a].x][thread1Quene[a].y][thread1Quene[a].z] = true;
delete thread1Quene[a].chk;
thread1Quene[a].exists = false;
}
}
}
//Called by Thread1 - Loader
void world::thread1loop()
{
while (running)
{
boost::mutex::scoped_lock lock(mMain);
bool changed=false;
for(int a=0;a<thread1QueneLimit;a++)
{
if (thread1Quene[a].exists==true)
{
signed int xCur=thread1Quene[a].x+xOffset-HALFCLIPDIST;
signed int yCur=thread1Quene[a].y+yOffset-HALFCLIPDIST;
signed int zCur=thread1Quene[a].z+zOffset-HALFCLIPDIST;
thread1Quene[a].chk = new chunk(xCur,yCur,zCur);
thread1Quene[a].exists = true;
//cout << xCur << "\n" << yCur << "\n";
//Writer->readChunk(xCur,yCur,zCur,iChunkX,iChunkY,iChunkZ);
//Writer->writeChunk(xCur,yCur,zCur,iChunkX,iChunkY,iChunkZ);
//changed=true;
}
}
if (changed)
{
bufferInitAll();
cout << "-------------------------------------------------! New Chunks added by thread 2!-------------------------------------------------\n";
}
}
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!