Demo:
http://stupidfresh.info/demo.rar
Help wanted page:
http://www.gamedev.net/community/forums/topic.asp?topic_id=490331
That's what I'm working with.
I'm glad everyone seems to agree that the server should have no problems keeping up. This will be my first attempt at making a large-scale server. So far it sounds like it will be easier than I thought. I have some winsock experience, I was just worried about cpu usage on the server. Hopefully it's not going to be too much of a problem.
It's a shared universe.
Handling large amounts of enemies
Quote:everyone seems to agree that the server should have no problems keeping up
Don't assume that that will be the case -- if you implement something wrong, it's very easy to make the server choke. However, it should be possible and straightforward to implement the design you've described so far, without choking a modern server computer. What we're saying is that you "just" need competent implementation -- not rocket science or secret super-inventions.
I wanted to point out that:
and:
is not the same thing. You're looking for:
count++;enemyindex[count]=count_index;
and:
enemyindex[count++]=count_index;
is not the same thing. You're looking for:
enemyindex[++count]=count_index;
Quote:
Bagheera
I wanted to point out that:
count++;
enemyindex[count]=count_index;
and:
enemyindex[count++]=count_index;
is not the same thing. You're looking for:
enemyindex[++count]=count_index;
You're right. Good call. I had it wrong the first time.
The first code would start counting at 1.
I needed to start at 0 instead.
Thanks for pointing this out.
Quote:
hplus0603
Quote:
everyone seems to agree that the server should have no problems keeping up
Don't assume that that will be the case -- if you implement something wrong, it's very easy to make the server choke. However, it should be possible and straightforward to implement the design you've described so far, without choking a modern server computer. What we're saying is that you "just" need competent implementation -- not rocket science or secret super-inventions.
Ok we shall see if I have what it takes. I'm pretty comfortable with winsock, so I feel good about it.
I did some work on it yesterday:
enemies move on timers
enemies change direction on timers
enemies collide with walls
enemies show thrust when moving
tweaked the render code
added background music
Maybe you could tell me what would be the normal way to
split the world into a grid? I need to do this because a 32bit int
can't hold the x,y coords. Is this what a quad tree would be good for?
Quadtrees are alright, but if you can sacrifice the RAM then I'd say go with a uniform grid. As in make a Cell class. Then make a multidimensional array of them. The cell class has a linked list of entities. So you insert objects into the cells. It's extremely easy to cull objects and serialize what you need and don't need since you know every player's view rectangle then you just expand it a bit and it normally works out well. There's more advanced methods, but that should get you started.
Another commonly used structure is a hash grid. It's like a grid, but instead of addressing using array indexing, you address based on the [x,y] tuple as a hash key. The nice thing about that is that, if there are large sparse areas in your world, then you don't waste storage for those.
Here's some example code I've come up with.
Does this look reasonable? I haven't tested it yet.
[Edited by - 00arch00 on April 17, 2008 11:30:10 PM]
Does this look reasonable? I haven't tested it yet.
typedef struct ns { int enemy_id; int enemy_x; int enemy_y; struct ns *next;} node; node *list_add(node **p, int id, int x, int y) { /* some compilers don't require a cast of return value for malloc */ node *n = (node *)malloc(sizeof(node)); if (n == NULL) return NULL; n->next = *p; *p = n; n->enemy_id = id; n->enemy_x = x; n->enemy_y = y; return *p;} void list_remove(node **p) { /* remove head */ if (*p != NULL) { node *n = *p; *p = (*p)->next; free(n); }} node **list_search(node **n, int id) { while (*n != NULL) { if ((*n)->enemy_id == id) { return n; } n = &(*n)->next; } return NULL;} void list_print(node *n) { if (n == NULL) { printf("list is empty\n"); } while (n != NULL) { printf("print current_node:%p\n next_node:%p\n enemy_id:%d\n enemy_x:%d\n enemy_y:%d\n\n", n, n->next, n->enemy_id,n->enemy_x,n->enemy_y); n = n->next; }}class cell{ node *n=NULL; void add_enemy(int id, int x, int y) { list_add(&n, id, x, y); } void remove_enemy(int id) { list_remove(list_search(&n, id)); } void send_enemies() { int enemy_id[sizeof(node)]; int enemy_x[sizeof(node)]; int enemy_y[sizeof(node)]; //Fill arrays with enemy data while (n != NULL) { enemy_id=n->enemy_id; enemy_x=n->enemy_x; enemy_y=n->enemy_y; n = n->next; } //Pseudocode send arrays //send(client_id,n->enemy_id[],n->enemy_x[],n->enemy_y[]); }}; void initialize_enemies(){ cell * map_cell = new cell[hcells][vcells]; for (int i=0;i<total_enemies-1;i++) { //Assign random x and y coordinates to enemy int x=rand()%cell_size; int y=rand()%cell_size; //Add enemy to a random cell map_cell[rand()%hcells][rand()%vcells].add_enemy(i,x,y); }}void send_enemies(cell * map_cell, int h, int v){ if (h>=1&&v>=1) { map_cell[h][v].send_enemies(); map_cell[h-1][v].send_enemies(); map_cell[h+1][v].send_enemies(); map_cell[h][v-1].send_enemies(); map_cell[h-1][v-1].send_enemies(); map_cell[h+1][v-1].send_enemies(); map_cell[h][v+1].send_enemies(); map_cell[h-1][v+1].send_enemies(); map_cell[h+1][v+1].send_enemies(); } else if (v==0) { map_cell[h][v].send_enemies(); map_cell[h-1][v].send_enemies(); map_cell[h+1][v].send_enemies(); map_cell[h][v+1].send_enemies(); map_cell[h-1][v+1].send_enemies(); map_cell[h+1][v+1].send_enemies(); } else if (h==0) { map_cell[h][v].send_enemies(); map_cell[h+1][v].send_enemies(); map_cell[h][v-1].send_enemies(); map_cell[h+1][v-1].send_enemies(); map_cell[h][v+1].send_enemies(); map_cell[h+1][v+1].send_enemies(); }} #define total_enemies 10000#define cell_size 1000#define hcells 1000#define vcells 1000#include <stdio.h> /* for printf */#include <stdlib.h> /* for malloc */ int main(){ initialize_enemies(); // send nearby enemies to players for (i=0;i<total_players-1;i++) { player.h=players horizontal cell player.v=players vertical cell send_enemies(&map_cell,player.h,player.v); }}
[Edited by - 00arch00 on April 17, 2008 11:30:10 PM]
Hmm. The problem with C code is that 98% of it is boilerplate for simple stuff that you could just use the C++ standard library to do. I kind of switch off when I start seeing '->next' anywhere, these days.
I suggest you test it, or ask a more precise question about it.
I suggest you test it, or ask a more precise question about it.
(well you just reminded me why I never learned C, use C++ and the STL)
//Add enemy to a random cell map_cell[rand()%hcells][rand()%vcells].add_enemy(i,x,y);
hmm, I think you missed the idea.
You want to create the entities with random positions then calculate their AABB and insert them into the grid. The entities will hold onto an array of their list nodes. So when inserting them into a cell also add the cell to the entity. This allows for O(1) insertion and O(1) deletion (basically. Don't overthink it).
After you create the array of entities go through and calculate it's AABB. Then from the points
okay that nested for loop might be right, but also for the sake of sanity put in checks on the integers to make sure they don't go out of bounds. If your physics suck and an object slides outside of the spatial partitioning handle it and such or bad things will happen.
So moving objects are removed and inserted every frame. That's the naive approach and works well. More advanced insertion methods exist such as swept insertion, which means inserting it along its path of motion to enable physics to work for fast moving objects. Picture an object moving to the right and another object diagonal of it to the right and down is moving up. If they are moving very fast and you check the object moving right first and check all the objects along its path you will find situations where it will collide with an object but because the other object wasn't inserted along its path of motion that object won't be checked. Some fun algorithms to write are circle swept, AABB swept and convex polygon swept. Again a lot of these more advanced algorithms use the idea of 3DDDA for optimization. Bullets or rays are common reasons.
//Add enemy to a random cell map_cell[rand()%hcells][rand()%vcells].add_enemy(i,x,y);
hmm, I think you missed the idea.
You want to create the entities with random positions then calculate their AABB and insert them into the grid. The entities will hold onto an array of their list nodes. So when inserting them into a cell also add the cell to the entity. This allows for O(1) insertion and O(1) deletion (basically. Don't overthink it).
After you create the array of entities go through and calculate it's AABB. Then from the points
for(int x = int(entity.AABB.min.x/cellSize); x <= int(entity.AABB.max.x/cellSize); ++x){ for(int y = int(entity.AABB.min.y/cellSize); y <= int(entity.AABB.max.y/cellSize); ++y) { //grid[x][y].Insert(entity);//will add it in the cell and also insert add the list node to an array in the entity, the entity has a RemoveFromGrid function. }}
okay that nested for loop might be right, but also for the sake of sanity put in checks on the integers to make sure they don't go out of bounds. If your physics suck and an object slides outside of the spatial partitioning handle it and such or bad things will happen.
So moving objects are removed and inserted every frame. That's the naive approach and works well. More advanced insertion methods exist such as swept insertion, which means inserting it along its path of motion to enable physics to work for fast moving objects. Picture an object moving to the right and another object diagonal of it to the right and down is moving up. If they are moving very fast and you check the object moving right first and check all the objects along its path you will find situations where it will collide with an object but because the other object wasn't inserted along its path of motion that object won't be checked. Some fun algorithms to write are circle swept, AABB swept and convex polygon swept. Again a lot of these more advanced algorithms use the idea of 3DDDA for optimization. Bullets or rays are common reasons.
Thanks a lot for the replies.
I had a feeling that old C code wouldn't work.
I couldn't get it to compile, MSVC++ tells me malloc free and NULL are
undeclared even when I include <stdlib.h>. It also gives me a redefinition error. If I omit stdlib.h it stops complaining about the redefinition but still complains about malloc...
That's just the first linked list code I ran across.
Still it shows the concept of what I'm trying to do with the cell class.
Thanks for pointing me toward the STL though.
I was in a hurry, it was late, just wanted to see if my interpretation of the concept was accurate.
That looks a lot like the way I had it at first.
I had something like:
map_cell[player[0].x/cellsize][player[0].y/cellsize].add_enemy(i);
But wouldn't player[0].x, player[0].y still be restricted by
the size of a 32 bit integer if I did that?
It looks like the code you have would add every pixel of the entity's sprite as a seperate list member.
I'm seeing something like:
for (int x=player[0].x-32/cellsize;x<=int(player[0].x+32/cellsize);++x)
{
for (int y=player[0].y-32/cellsize;y<=int(player[0].y+32/cellsize);++y)
{
grid[x][y].Insert(entity);
}
}
Looks like that would insert entity 64*64 times for a 64*64 bounding box.
grid[player[0].x-32][player[0].y-32].Insert(entity);
grid[player[0].x-32][player[0].y-31].Insert(entity);
grid[player[0].x-32][player[0].y-30].Insert(entity);
etc...
As far as the 0(1) insertion goes, I read that inserting into the middle of a linked list has 0(1) insertion time, but indexing is 0(n).
I had a feeling that old C code wouldn't work.
I couldn't get it to compile, MSVC++ tells me malloc free and NULL are
undeclared even when I include <stdlib.h>. It also gives me a redefinition error. If I omit stdlib.h it stops complaining about the redefinition but still complains about malloc...
That's just the first linked list code I ran across.
Still it shows the concept of what I'm trying to do with the cell class.
Thanks for pointing me toward the STL though.
I was in a hurry, it was late, just wanted to see if my interpretation of the concept was accurate.
Quote:
for(int x = int(entity.AABB.min.x/cellSize); x <= int(entity.AABB.max.x/cellSize); ++x)
{
for(int y = int(entity.AABB.min.y/cellSize); y <= int(entity.AABB.max.y/cellSize); ++y)
{
//grid[x][y].Insert(entity);//will add it in the cell and also insert add the list node to an array in the entity, the entity has a RemoveFromGrid function.
}
}
That looks a lot like the way I had it at first.
I had something like:
map_cell[player[0].x/cellsize][player[0].y/cellsize].add_enemy(i);
But wouldn't player[0].x, player[0].y still be restricted by
the size of a 32 bit integer if I did that?
It looks like the code you have would add every pixel of the entity's sprite as a seperate list member.
I'm seeing something like:
for (int x=player[0].x-32/cellsize;x<=int(player[0].x+32/cellsize);++x)
{
for (int y=player[0].y-32/cellsize;y<=int(player[0].y+32/cellsize);++y)
{
grid[x][y].Insert(entity);
}
}
Looks like that would insert entity 64*64 times for a 64*64 bounding box.
grid[player[0].x-32][player[0].y-32].Insert(entity);
grid[player[0].x-32][player[0].y-31].Insert(entity);
grid[player[0].x-32][player[0].y-30].Insert(entity);
etc...
As far as the 0(1) insertion goes, I read that inserting into the middle of a linked list has 0(1) insertion time, but indexing is 0(n).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement