[Super-tux-commit] supertux/src collision_grid.cpp,NONE,1.1 collision_grid.h,NONE,1.1 sector.cpp,1.5
Brought to you by:
wkendrick
Menu
▾
▴
[Super-tux-commit] supertux/src collision_grid.cpp,NONE,1.1 collision_grid.h,NONE,1.1 sector.cpp,1.56,1.57 sector.h,1.28,1.29
|
From: Matze B. <mat...@us...> - 2004-11-29 16:04:27
|
Update of /cvsroot/super-tux/supertux/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv18135/src Modified Files: sector.cpp sector.h Added Files: collision_grid.cpp collision_grid.h Log Message: started work on a collision grid class to speedup collision detection. Doesn't work for moving objects yet, but brings speed in area42 from 5fps back to 100fps on my box (still I get 300-400fps in other levels) --- NEW FILE: collision_grid.cpp --- #include <config.h> #include <iostream> #include "collision_grid.h" #include "special/collision.h" #include "sector.h" static const float DELTA = .001; CollisionGrid::CollisionGrid(float newwidth, float newheight) : width(newwidth), height(newheight), cell_width(128), cell_height(128) { cells_x = size_t(width / cell_width) + 1; cells_y = size_t(height / cell_height) + 1; grid.resize(cells_x * cells_y); } CollisionGrid::~CollisionGrid() { for(GridEntries::iterator i = grid.begin(); i != grid.end(); ++i) { GridEntry* entry = *i; while(entry) { GridEntry* nextentry = entry->next; delete entry; entry = nextentry; } } } void CollisionGrid::add_object(MovingObject* object) { #ifdef DEBUG // make sure the object isn't already in the grid for(Objects::iterator i = objects.begin(); i != objects.end(); ++i) { ObjectWrapper* wrapper = *i; if(wrapper->object == object) assert(false); } assert(object != 0); #endif ObjectWrapper* wrapper = new ObjectWrapper; wrapper->object = object; wrapper->timestamp = 0; wrapper->dest = object->bbox; objects.push_back(wrapper); wrapper->id = objects.size()-1; const Rectangle& bbox = object->bbox; for(float y = bbox.p1.y; y < bbox.p2.y; y += cell_height) { for(float x = bbox.p1.x; x < bbox.p2.x; x += cell_width) { int gridx = int(x / cell_width); int gridy = int(y / cell_height); if(gridx < 0 || gridy < 0 || gridx >= int(cells_x) || gridy >= int(cells_y)) { std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n"; continue; } GridEntry* entry = new GridEntry; entry->object_wrapper = wrapper; entry->next = grid[gridy*cells_x + gridx]; grid[gridy*cells_x + gridx] = entry; } } } void CollisionGrid::remove_object(MovingObject* object) { ObjectWrapper* wrapper = 0; for(Objects::iterator i = objects.begin(); i != objects.end(); ++i) { if((*i)->object == object) { wrapper = *i; objects.erase(i); break; } } assert(wrapper != 0); const Rectangle& bbox = wrapper->dest; for(float y = bbox.p1.y; y < bbox.p2.y; y += cell_height) { for(float x = bbox.p1.x; x < bbox.p2.x; x += cell_width) { int gridx = int(x / cell_width); int gridy = int(y / cell_height); if(gridx < 0 || gridy < 0 || gridx >= int(cells_x) || gridy >= int(cells_y)) { std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n"; continue; } remove_object_from_gridcell(gridy*cells_x + gridx, object); } } delete wrapper; } void CollisionGrid::move_object(MovingObject* object) { const Rectangle& bbox = object->bbox; for(float y = bbox.p1.y; y < bbox.p2.y; y += cell_height) { for(float x = bbox.p1.x; x < bbox.p2.x; x += cell_width) { int gridx = int(x / cell_width); int gridy = int(y / cell_height); if(gridx < 0 || gridy < 0 || gridx >= int(cells_x) || gridy >= int(cells_y)) { std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n"; continue; } // TODO } } } void CollisionGrid::check_collisions() { for(Objects::iterator i = objects.begin(); i != objects.end(); ++i) { ObjectWrapper* wrapper = *i; MovingObject* object = wrapper->object; if(!object->is_valid()) continue; if(object->get_flags() & GameObject::FLAG_NO_COLLDET) { object->bbox.move(object->movement); object->movement = Vector(0, 0); continue; } // hack for now... Sector::current()->collision_tilemap(object, 0); collide_object(wrapper); object->bbox.move(object->get_movement()); object->movement = Vector(0, 0); } } void CollisionGrid::collide_object(ObjectWrapper* wrapper) { static int timestamp = 0; timestamp++; const Rectangle& bbox = wrapper->object->bbox; for(float y = bbox.p1.y; y < bbox.p2.y; y += cell_height) { for(float x = bbox.p1.x; x < bbox.p2.x; x += cell_width) { int gridx = int(x / cell_width); int gridy = int(y / cell_height); if(gridx < 0 || gridy < 0 || gridx >= int(cells_x) || gridy >= int(cells_y)) { std::cerr << "Object out of range: " << gridx << ", " << gridy << "\n"; continue; } for(GridEntry* entry = grid[gridy*cells_x + gridx]; entry; entry = entry->next) { ObjectWrapper* wrapper2 = entry->object_wrapper; // only check each object once (even if it is in multiple cells) if(wrapper2->timestamp == timestamp) continue; // don't collide with objects we already collided with if(wrapper2->id <= wrapper->id) continue; wrapper->timestamp = timestamp; collide_object_object(wrapper, wrapper2); } } } } void CollisionGrid::collide_object_object(ObjectWrapper* wrapper, ObjectWrapper* wrapper2) { CollisionHit hit; MovingObject* object1 = wrapper->object; MovingObject* object2 = wrapper2->object; Rectangle dest1 = object1->get_bbox(); dest1.move(object1->get_movement()); Rectangle dest2 = object2->get_bbox(); dest2.move(object2->get_movement()); Vector movement = object1->get_movement() - object2->get_movement(); if(Collision::rectangle_rectangle(hit, dest1, movement, dest2)) { HitResponse response1 = object1->collision(*object2, hit); hit.normal *= -1; HitResponse response2 = object2->collision(*object1, hit); if(response1 != CONTINUE) { if(response1 == ABORT_MOVE) object1->movement = Vector(0, 0); if(response2 == CONTINUE) object2->movement += hit.normal * (hit.depth + DELTA); } else if(response2 != CONTINUE) { if(response2 == ABORT_MOVE) object2->movement = Vector(0, 0); if(response1 == CONTINUE) object1->movement += -hit.normal * (hit.depth + DELTA); } else { object1->movement += -hit.normal * (hit.depth/2 + DELTA); object2->movement += hit.normal * (hit.depth/2 + DELTA); } } } void CollisionGrid::remove_object_from_gridcell(int gridcell, MovingObject* object) { GridEntry* lastentry = 0; GridEntry* entry = grid[gridcell]; while(entry) { if(entry->object_wrapper->object == object) { if(lastentry == 0) { grid[gridcell] = entry->next; } else { lastentry->next = entry->next; } delete entry; return; } lastentry = entry; entry = entry->next; }; std::cerr << "Couldn't find object in cell.\n"; } Index: sector.h =================================================================== RCS file: /cvsroot/super-tux/supertux/src/sector.h,v retrieving revision 1.28 retrieving revision 1.29 diff -u -d -r1.28 -r1.29 --- sector.h 28 Nov 2004 14:56:49 -0000 1.28 +++ sector.h 29 Nov 2004 16:03:32 -0000 1.29 @@ -40,19 +40,11 @@ class Writer; } -class InteractiveObject; -class Background; class Player; class Camera; -class Trampoline; -class FlyingPlatform; class TileMap; -class Upgrade; class Bullet; -class SmokeCloud; -class Particles; -class BadGuy; -class Tile; +class CollisionGrid; struct SpawnPoint { @@ -115,8 +107,10 @@ /** Get total number of badguys */ int get_total_badguys(); -private: + // make this private again soon void collision_tilemap(MovingObject* object, int depth); + +private: void collision_object(MovingObject* object1, MovingObject* object2); void load_music(); @@ -142,8 +136,6 @@ std::vector<Bullet*> bullets; public: // TODO make this private again - typedef std::vector<InteractiveObject*> InteractiveObjects; - InteractiveObjects interactive_objects; typedef std::vector<GameObject*> GameObjects; GameObjects gameobjects; @@ -157,6 +149,8 @@ SpawnPoints spawnpoints; int currentmusic; + + CollisionGrid* grid; }; #endif Index: sector.cpp =================================================================== RCS file: /cvsroot/super-tux/supertux/src/sector.cpp,v retrieving revision 1.56 retrieving revision 1.57 diff -u -d -r1.56 -r1.57 --- sector.cpp 28 Nov 2004 17:19:25 -0000 1.56 +++ sector.cpp 29 Nov 2004 16:03:31 -0000 1.57 @@ -42,6 +42,7 @@ #include "gameloop.h" #include "resources.h" #include "statistics.h" +#include "collision_grid.h" #include "special/collision.h" #include "math/rectangle.h" #include "math/aatriangle.h" @@ -73,6 +74,8 @@ song_title = "Mortimers_chipdisko.mod"; player = new Player(); add_object(player); + + grid = new CollisionGrid(32000, 32000); } Sector::~Sector() @@ -80,6 +83,8 @@ update_game_objects(); assert(gameobjects_new.size() == 0); + delete grid; + for(GameObjects::iterator i = gameobjects.begin(); i != gameobjects.end(); ++i) { delete *i; @@ -485,29 +490,42 @@ /** cleanup marked objects */ for(std::vector<GameObject*>::iterator i = gameobjects.begin(); i != gameobjects.end(); /* nothing */) { - if((*i)->is_valid() == false) { - Bullet* bullet = dynamic_cast<Bullet*> (*i); - if(bullet) { - bullets.erase( - std::remove(bullets.begin(), bullets.end(), bullet), - bullets.end()); - } - delete *i; - i = gameobjects.erase(i); - } else { + GameObject* object = *i; + + if(object->is_valid()) { ++i; + continue; + } + + Bullet* bullet = dynamic_cast<Bullet*> (object); + if(bullet) { + bullets.erase( + std::remove(bullets.begin(), bullets.end(), bullet), + bullets.end()); } + MovingObject* movingobject = dynamic_cast<MovingObject*> (object); + if(movingobject) { + grid->remove_object(movingobject); + } + delete *i; + i = gameobjects.erase(i); } /* add newly created objects */ for(std::vector<GameObject*>::iterator i = gameobjects_new.begin(); i != gameobjects_new.end(); ++i) { - Bullet* bullet = dynamic_cast<Bullet*> (*i); + GameObject* object = *i; + + Bullet* bullet = dynamic_cast<Bullet*> (object); if(bullet) bullets.push_back(bullet); - TileMap* tilemap = dynamic_cast<TileMap*> (*i); + MovingObject* movingobject = dynamic_cast<MovingObject*> (object); + if(movingobject) + grid->add_object(movingobject); + + TileMap* tilemap = dynamic_cast<TileMap*> (object); if(tilemap && tilemap->is_solid()) { if(solids == 0) { solids = tilemap; @@ -516,7 +534,7 @@ } } - Camera* camera = dynamic_cast<Camera*> (*i); + Camera* camera = dynamic_cast<Camera*> (object); if(camera) { if(this->camera != 0) { std::cerr << "Warning: Multiple cameras added. Ignoring."; @@ -525,7 +543,7 @@ this->camera = camera; } - gameobjects.push_back(*i); + gameobjects.push_back(object); } gameobjects_new.clear(); } @@ -674,6 +692,9 @@ void Sector::collision_handler() { +#if 0 + grid->check_collisions(); +#else for(std::vector<GameObject*>::iterator i = gameobjects.begin(); i != gameobjects.end(); ++i) { GameObject* gameobject = *i; @@ -709,6 +730,7 @@ movingobject->bbox.move(movingobject->get_movement()); movingobject->movement = Vector(0, 0); } +#endif } bool --- NEW FILE: collision_grid.h --- #ifndef __COLLISION_GRID_H__ #define __COLLISION_GRID_H__ #include <vector> #include "special/moving_object.h" using namespace SuperTux; /** * A rectangular grid to keep track of all moving game objects. It allows fast * queries for all objects in a rectangular area. */ class CollisionGrid { public: CollisionGrid(float width, float height); ~CollisionGrid(); void add_object(MovingObject* object); void remove_object(MovingObject* object); void move_object(MovingObject* object); void check_collisions(); private: struct ObjectWrapper { MovingObject* object; Rectangle dest; /** (pseudo) timestamp. When reading from the grid the timestamp is * changed so that you can easily avoid reading an object multiple times * when it is in several cells that you check. */ int timestamp; /// index in the objects vector int id; }; /** Element for the single linked list in each grid cell */ struct GridEntry { GridEntry* next; ObjectWrapper* object_wrapper; }; void remove_object_from_gridcell(int gridcell, MovingObject* object); void collide_object(ObjectWrapper* wrapper); void collide_object_object(ObjectWrapper* wrapper, ObjectWrapper* wrapper2); typedef std::vector<GridEntry*> GridEntries; GridEntries grid; typedef std::vector<ObjectWrapper*> Objects; Objects objects; size_t cells_x, cells_y; float width; float height; float cell_width; float cell_height; }; extern CollisionGrid* bla; #endif |
