The Excellent Code Thread

For discussion of the code running behind the game

Moderator: Staff

User avatar
visage
Former Staff
Posts: 711
Joined: Sat Sep 03, 2005 9:19 pm
Location: USA
Contact:

The Excellent Code Thread

Postby visage » Fri Apr 07, 2006 3:57 pm

I am going above Roots and not even asking if it is alright to sticky this. I am just going ahead and doing it ;)

Alright programmers. I think it is totally unfair that artists get to debut their work for all to see. We on the other hand commit our code and never really get our little gems recognized unless someone else happens to look at our code.

This sticky is where you should post any code you wrote that you think is particularly cool, or perhaps someone elses code you found that you particularly like.

As well, consider this a place to post code you might want input on. Artists are EXPECTED to show WIP, I don't see why we cant take a page out of that book. We often discuss design with one another, but I think it is high time we begin discussing actual code!

As well, the code can just be representative and does not have to be technically impressive. Perhaps it is the last line you wrote to finish the module you are working on.

So post away!


Guidelines for code sharing
    > Keep the code short and sweet.
    If the code you are sharing is over 200 lines long, do *not* post it directly into this thread. Provide a SVN link to the file with the code ( http://svn.sourceforge.net/viewcvs.cgi/allacrost/ )

    > Don't post every little code segment you write.
    Only share what you consider the "cream of the crop"

    > Share your code in moderation.
    Several of us have already thousands of lines of code written for Allacrost. Don't attempt to show us all of your best code at once.

    > Give feedback (hopefully positive) on each other's code posts.
    This thread is supposed to serve as a reward mechanism for us. But on the other hand if you find something wrong or something that could use improvement in someone's code, don't be afraid to speak out and tell them about it.
User avatar
Roots
Dictator
Posts: 8665
Joined: Wed Jun 16, 2004 6:07 pm
Location: Austin TX
Contact:

Postby Roots » Sat Apr 08, 2006 12:58 am

Cool idea. :) How about moving this to the public programming forum though? If we're going to show off, we might as well do it on a grander scale. :cool:
Image
User avatar
visage
Former Staff
Posts: 711
Joined: Sat Sep 03, 2005 9:19 pm
Location: USA
Contact:

Postby visage » Sat Apr 08, 2006 1:47 am

Thats cool with me. I think you have to move it though.
User avatar
visage
Former Staff
Posts: 711
Joined: Sat Sep 03, 2005 9:19 pm
Location: USA
Contact:

Postby visage » Mon May 15, 2006 4:31 pm

Code: Select all

ReadDataDescriptor read_data;
string fileName = "dat/objects/" + name + ".lua";
if (!read_data.OpenFile(fileName.c_str())) {
     cout << "GLOBAL ERROR: failed to load weapon file: " << name << endl;
}
else {
     _damage_amount->volt = read_data.ReadInt("volt_damage");
     ....
}


This code itself isn't particularly amazing. In fact, it doesn't even represent anything impressive...except for the underlying functionality. I don't know who wrote this Lua stuff, but it is shear abstracted brilliance. Wow. It is so easy to use. :bow: You could probably make it into a separate library and distribute it to other teams! I love it!
User avatar
gorzuate
Developer
Posts: 2575
Joined: Thu Jun 17, 2004 3:03 am
Location: Hermosa Beach, CA
Contact:

Postby gorzuate » Mon May 15, 2006 4:36 pm

It should hopefully get even more functionality in the next couple of weeks, right Zorbfish? ;)
Image
User avatar
Roots
Dictator
Posts: 8665
Joined: Wed Jun 16, 2004 6:07 pm
Location: Austin TX
Contact:

Postby Roots » Mon May 15, 2006 5:34 pm

visage wrote:

Code: Select all

ReadDataDescriptor read_data;
string fileName = "dat/objects/" + name + ".lua";
if (!read_data.OpenFile(fileName.c_str())) {
     cout << "GLOBAL ERROR: failed to load weapon file: " << name << endl;
}
else {
     _damage_amount->volt = read_data.ReadInt("volt_damage");
     ....
}


This code itself isn't particularly amazing. In fact, it doesn't even represent anything impressive...except for the underlying functionality. I don't know who wrote this Lua stuff, but it is shear abstracted brilliance. Wow. It is so easy to use. :bow: You could probably make it into a separate library and distribute it to other teams! I love it!


snipe714 did the initial back-end routines and C++/Lua binding work. I was the one that abstracted it into the ReadDataDescriptor and WriteDataDescriptor classes to interface with our Lua scripts. I'm glad you like it. :D I think Zorb is going to make it much better though, particularly when you can modify variables in the middle of a file. :D
Image
User avatar
Steu
Developer
Posts: 926
Joined: Thu Jan 05, 2006 10:41 pm
Location: Medicine Hat
Contact:

Postby Steu » Wed May 17, 2006 12:42 am

Was going through the Inventory window setup code today, and found this one line I was particularly proud of.

Code: Select all

// Set the size of the option box
// Calculate the number of rows, this is dividing by row_width, and if there is a remainder > 0
// add one more row for the remainder.
uint32 row_width = 4;
_inventory_items.SetSize(row_width, inv.size() / row_width + ((inv.size() % row_width) > 0 ? 1 : 0));


All it does is dynamically change the size, usually the number of rows in the option box depending on the number of items contained in the inventory. The row_width variable just specifies the number of columns for the inventory screen.

Note: For some reason I love the ? : operator and use it far too much :heh:
Last edited by Steu on Wed May 17, 2006 2:09 am, edited 1 time in total.
User avatar
Roots
Dictator
Posts: 8665
Joined: Wed Jun 16, 2004 6:07 pm
Location: Austin TX
Contact:

Postby Roots » Wed May 17, 2006 1:51 am

Looks great, but it needs a comment!!! :eyespin:
Image
User avatar
Steu
Developer
Posts: 926
Joined: Thu Jan 05, 2006 10:41 pm
Location: Medicine Hat
Contact:

Postby Steu » Wed May 17, 2006 2:09 am

There is, I just didn't copy it. I'll add it in.
User avatar
Roots
Dictator
Posts: 8665
Joined: Wed Jun 16, 2004 6:07 pm
Location: Austin TX
Contact:

Postby Roots » Wed May 17, 2006 2:10 am

Then you may keep your head on your shoulders.....for now :devil:
Image
User avatar
Roots
Dictator
Posts: 8665
Joined: Wed Jun 16, 2004 6:07 pm
Location: Austin TX
Contact:

Postby Roots » Wed May 17, 2006 2:16 am

This code comes from map.cpp for the MapMode code. Its purpose is to collect information about the current view scene that is used to draw all of the tiles/sprites/images of the map in the correct way. It may not look like anything special. After all, it's mostly just a bunch of if statements and add/subtract operations to calculate offsets. But if you look deeply into it, it's pretty rough and difficult to understand, even with the comments I left.

First the function assumes that the object that the map camera is focused on is not moving and is located smack on the center of some tile in the center of the map. Initial draw positions/offsets are calculated from this assumption. But if the focused object *is* moving, then it has to figure out which direction its moving and how far it has gotten to the next tile. This is used to calculate an X/Y offset for the camera. But it doesn't end there. Then the code has to check whether the object focused on by the camera is near the edges of the map. If it is, then another offset needs to be calculated and the camera has to remain still while the object walks around that edge.

This code was a bitch to get working correctly, despite its initial innocent appearance. :eyespin: But it works now, and it works damn well. :cool:


SVN code link, lines 920-1012: void MapMode::_GetDrawInfo() function.

Code: Select all

// Determines things like our starting tiles
void MapMode::_GetDrawInfo() {
   // ************* (1) Set the default drawing positions for the tiles ****************
   // Begin drawing from the top left corner
   _draw_info.c_pos = -0.5f;
   _draw_info.r_pos = 0.5f;

   // By default draw 32 + 1 columns and 24 + 1 rows
   _draw_info.c_draw = static_cast<uint8>(SCREEN_COLS) + 1;
   _draw_info.r_draw = static_cast<uint8>(SCREEN_ROWS) + 1;

   // The default starting tile row and column is relative to the focused sprite's current position.
   _draw_info.c_start = static_cast<int16>(_focused_object->col_position - (static_cast<int32>(SCREEN_COLS) / 2));
   _draw_info.r_start = static_cast<int16>(_focused_object->row_position - (static_cast<int32>(SCREEN_ROWS) / 2));

   // *** (2) Modify drawing positions if focused sprite is currently moving ***

   if (_focused_object->status & IN_MOTION) {
      float offset = _focused_object->step_count / _focused_object->step_speed;
      if (_focused_object->direction & (WEST | NW_NORTH | NW_WEST | SW_SOUTH | SW_WEST)) {
         if (offset < 0.5f) {
            _draw_info.c_pos += offset;
            _draw_info.c_start++;
         }
         else {
            _draw_info.c_pos -= 1.0f - offset;
         }
      }
      else if (_focused_object->direction & (EAST | NE_NORTH | NE_EAST | SE_SOUTH | SE_EAST)) {
         if (offset < 0.5f) {
            _draw_info.c_pos -= offset;
            _draw_info.c_start--;
         }
         else {
            _draw_info.c_pos += 1.0f - offset;
         }
      }

      if (_focused_object->direction & (NORTH | NW_WEST | NW_NORTH | NE_EAST | NE_NORTH)) {
         if (offset < 0.5f) {
            _draw_info.r_pos += offset;
            _draw_info.r_start++;
         }
         else {
            _draw_info.r_pos -= 1.0f - offset;
         }
      }
      else if (_focused_object->direction & (SOUTH | SW_WEST | SW_SOUTH | SE_EAST | SE_SOUTH)) {
         if (offset < 0.5f) {
            _draw_info.r_pos -= offset;
            _draw_info.r_start--;
         }
         else {
            _draw_info.r_pos += 1.0f - offset;
         }
      }
   }

   // *********************** (3) Check for special conditions **************************

   // Usually the map moves around the player, but when we encounter the edges of the map we
   // want the player to move around the map.

   // Exceeds the far-left side of the map
   if (_draw_info.c_start < 0) {
      _draw_info.c_start = 0;
      _draw_info.c_pos = 0.0f;
   }
   // Exceeds the far-right side of the map
   else if (_draw_info.c_start >= _col_count - static_cast<int32>(SCREEN_COLS)) {
      _draw_info.c_start = static_cast<int16>(_col_count - static_cast<int32>(SCREEN_COLS));
      _draw_info.c_pos = 0.0f;
   }
   // If our column position is exactly on the left edge of the screen, we draw one less column of tiles
   if (_draw_info.c_pos == 0.0f) {
      _draw_info.c_draw--;
   }

   // Exceeds the far-north side of the map
   if (_draw_info.r_start < 0) {
      _draw_info.r_start = 0;
      _draw_info.r_pos = 1.0f;
   }
   // Exceeds the far-south side of the map
   else if (_draw_info.r_start >= _row_count - static_cast<int32>(SCREEN_ROWS)) {
      _draw_info.r_start = static_cast<int16>(_row_count - static_cast<int32>(SCREEN_ROWS));
      _draw_info.r_pos = 1.0f;
   }
   // If the row position is exactly on the top of the screen, draw one less row of tiles
   if (_draw_info.r_pos == 1.0f) {
      _draw_info.r_draw--;
   }
} // MapMode::_GetDrawInfo()
Image
User avatar
MindFlayer
Developer
Posts: 688
Joined: Fri Jan 06, 2006 12:55 pm
Location: Kuopio / Tampere, Finland
Contact:

Postby MindFlayer » Wed Jul 19, 2006 8:46 pm

Roots asked me about how I did the Credits-screen so here it goes:

Basically I wanted a simple effect for fading in the text as well as scrolling it. I did both of them simultaneously and I think the result looks pretty neat.

Here's all of the update code required:

Code: Select all

// Updates the credits window
void CreditsScreen::UpdateWindow(int32 frameTime)
{
   _window.Update(frameTime);
   float color_alpha = _text_offset_y * 0.025f;
   float delta = static_cast<float>(frameTime) * 0.02f;
   _text_offset_y += delta; // Update text offset

   // Fade in the text by setting new text color with alpha value below 1.0f
   VideoManager->SetTextColor(Color(1.0f, 1.0f, 1.0f, (color_alpha > 1.0f) ? 1.0f : color_alpha));
}


And here's the rendering part:

Code: Select all

// Set clip region for the text and draw the visible part of it
VideoManager->Move(512.0f, 450 + _text_offset_y);
VideoManager->SetScissorRect(_window.GetScissorRect());
VideoManager->EnableScissoring(true);
VideoManager->DrawText(MakeWideString(_credits_text));
VideoManager->EnableScissoring(false);
}


_text_offset_y starts from 0.0f so alpha is 0 as well...

As you can see, everything works based on real-time, alpha-blending won't go over 1.0f, and I even update the background window as well in this code :) This is why I like working with the current engine. Even though it has some quirks (like slow rendering), everything necessary is in place, I just have to use 'em ! :cool:

(yeah, ?: keeps popping in these code snippets! :heh:)
User avatar
Roots
Dictator
Posts: 8665
Joined: Wed Jun 16, 2004 6:07 pm
Location: Austin TX
Contact:

Postby Roots » Wed Jul 19, 2006 9:20 pm

Wow, that is sweet! It took me a minute to look at it and figure out what the heck was going on. :heh: Yeah working with the video engine is great; the quirks are there because up until about May, it had not had the chance to undergo a thorough amount of testing. There are a lot of features in the video engine that I don't even know about yet so its really exciting to discover them at times. :D
Image
User avatar
MindFlayer
Developer
Posts: 688
Joined: Fri Jan 06, 2006 12:55 pm
Location: Kuopio / Tampere, Finland
Contact:

Postby MindFlayer » Thu Dec 28, 2006 12:13 pm

This post isn't about great code but more about my secret weapon against the evil, yet cute-looking bugs in the Allacrost code.

Here, take a look! :D
[img:1024:768]http://www.allacrost.org/staff/user/mindflayer/debug.PNG[/img]
(Just my way of saying that I love Visual C++'s debugger :hack:)
User avatar
Roots
Dictator
Posts: 8665
Joined: Wed Jun 16, 2004 6:07 pm
Location: Austin TX
Contact:

Postby Roots » Mon Jan 15, 2007 1:58 am

This is a new version of an earlier code snippet that I posted before. This deceptively simple function calculates the drawing position coordinates for every frame in map mode. The function changed significantly from the old tile-based movement system in the new free-range movement system, and it looks cleaner IMO. Here's how thf unction works now:


First, the function assumes that the map's camera is not on the edges of the map and assigns default positions. It uses the map camera's coordinates to calculate a number of measures:

- The coordinates of the tile that will be drawn in the top left corner of the screen (starting tile)
- The number of tile columns and rows that are visible on the screen, and thus should be drawn
- The map grid coordinates of the left, right, top, and bottom edges of the screen. These values are used by map objects to determine if they should be drawn on the screen or not.

Like last time, it then checks for conditions where the camera is along any side of the screen, and adjusts accordingly. Unlike last time, the movement direction of the map camera has absolutely no effect on the drawing coordinates (which is a good thing :)). Also just like last time, this code was again a bitch to get working correctly. I'm glad that this is the last time I have to work on this code. :heh:

Code: Select all

// Determines things like our starting tiles
void MapMode::_CalculateDrawInfo() {
   // ---------- (1) Set the default starting draw positions for the tiles (top left tile)

   // The camera's position is in terms of the 16x16 grid, which needs to be converted into 32x32 coordinates.
   float camera_x = static_cast<float>(_camera->x_position) + _camera->x_offset;
   float camera_y = static_cast<float>(_camera->y_position) + _camera->y_offset;

   // Determine the draw coordinates of the top left corner using the camera's current position
   _draw_info.tile_x_start = 1.0f - _camera->x_offset;
   if (IsOddNumber(_camera->x_position))
      _draw_info.tile_x_start -= 1.0f;

   _draw_info.tile_y_start = 2.0f - _camera->y_offset;
   if (IsOddNumber(_camera->y_position))
      _draw_info.tile_y_start -= 1.0f;

   // By default the map draws 32 + 1 columns and 24 + 1 rows of tiles, the maximum that can fit on the screen.
   _draw_info.num_draw_cols = TILE_COLS + 1;
   _draw_info.num_draw_rows = TILE_ROWS + 1;

   // The default starting tile row and column is relative to the map camera's current position.
   _draw_info.starting_col = (_camera->x_position / 2) - HALF_TILE_COLS;
   _draw_info.starting_row = (_camera->y_position / 2) - HALF_TILE_ROWS;

   // ---------- (2) Determine the coordinates for the screen edges on the map grid

   _draw_info.top_edge    = camera_y - HALF_SCREEN_ROWS;
   _draw_info.bottom_edge = camera_y + HALF_SCREEN_ROWS;
   _draw_info.left_edge   = camera_x - HALF_SCREEN_COLS;
   _draw_info.right_edge  = camera_x + HALF_SCREEN_COLS;

   // ---------- (3) Check for special conditions that modify the drawing state

   // Usually the map centers on the camera's position, but when the camera becomes close to
   // the edges of the map, we need to modify the drawing properties of the frame.

   // Camera exceeds the left boundary of the map
   if (_draw_info.starting_col < 0) {
      _draw_info.starting_col = 0;
      _draw_info.tile_x_start = 1.0f;
      _draw_info.left_edge = 0.0f;
      _draw_info.right_edge = SCREEN_COLS;
   }
   // Camera exceeds the right boundary of the map
   else if (_draw_info.starting_col + TILE_COLS >= _num_tile_cols) {
      _draw_info.starting_col = static_cast<int16>(_num_tile_cols - TILE_COLS);
      _draw_info.tile_x_start = 1.0f;
      _draw_info.right_edge = static_cast<float>(_num_tile_cols * 2);
      _draw_info.left_edge = _draw_info.right_edge - SCREEN_COLS;
   }

   // Camera exceeds the top boundary of the map
   if (_draw_info.starting_row < 0) {
      _draw_info.starting_row = 0;
      _draw_info.tile_y_start = 2.0f;
      _draw_info.top_edge = 0.0f;
      _draw_info.bottom_edge = SCREEN_ROWS;
   }
   // Camera exceeds the bottom boundary of the map
   else if (_draw_info.starting_row + TILE_ROWS >= _num_tile_rows) {
      _draw_info.starting_row = static_cast<int16>(_num_tile_rows - TILE_ROWS);
      _draw_info.tile_y_start = 2.0f;
      _draw_info.bottom_edge = static_cast<float>(_num_tile_rows * 2);
      _draw_info.top_edge = _draw_info.bottom_edge - SCREEN_ROWS;
   }

   // Check for the conditions where the tile images align perfectly with the screen and one less row or column of tiles is drawn
   if (IsFloatInRange(_draw_info.tile_x_start, 0.999, 1.001)) { // Is the value approximately equal to 1.0f?
      _draw_info.num_draw_cols--;
   }
   if (IsFloatInRange(_draw_info.tile_y_start, 1.999, 2.001)) { // Is the value approximately equal to 2.0f?
      _draw_info.num_draw_rows--;
   }
} // void MapMode::_CalculateDrawInfo()
Image
User avatar
Roots
Dictator
Posts: 8665
Joined: Wed Jun 16, 2004 6:07 pm
Location: Austin TX
Contact:

Postby Roots » Sun Apr 01, 2007 2:28 am

I wrote this piece over the past day or so for the map code to support tilesets. Its not too complex, but I think its nifty so I decided to share it.

The map file contains tile indeces for all three tile layers (lower, middle, and upper). The index represents the tileset image and the location within that image that the tile comes from. All tilesets are 512x512 pixels, which contain a total of 256 32x32 pixel tiles. Therefore, indeces 0-255 belong to tileset #0, 256-511 belong to tileset #1, etc.

Now what the code does below is the following:
> Figure out which tile images are referenced by the map and which are not
> Translate the tile indeces in all 3 layers to an index in the 1D _tile_images vector, which will contain all of the tiles images.
> Construct any animated tiles that are used by the map by parsing each tileset definition file
> Add all the tile images that are referenced, and discard those that are unused.

It sounds simple enough, but the code is a little bit :eyespin: about how it goes about doing this, even with the comments in place. :hack:

Code: Select all

void MapMode::_LoadTiles() {
   // Contains all of the tileset filenames used (string does not contain path information or file extensions)
   vector<string> tileset_filenames;
   // A container to temporarily retain all tile images loaded for each tileset. Each inner vector contains 256 StillImages
   vector<vector<StillImage> > tileset_images;
   // Used to determine whether each tile is used by the map or not. An entry of -1 indicates that particular tile is not used
   vector<int32> tile_references;
   // Temporarily holds all animated tile images. The map key is the value of the tile index, before translation
   map<uint32, AnimatedImage> tile_animations;

   // ---------- (1) Construct the map grid (contains map traveriblity information)

   _map_script.ReadOpenTable("map_grid");
   for (uint16 r = 0; r < _num_grid_rows; r++) {
      _map_grid.push_back(vector<uint32>());
      _map_script.ReadUIntVector(r, _map_grid.back());
   }
   _map_script.ReadCloseTable();
   // ---------- (2) Load in the map tileset images and initialize all map tiles

   _map_script.ReadStringVector("tileset_filenames", tileset_filenames);

   // Note: each tileset image is 512x512 pixels, yielding 256 32x32 pixel tiles each
   for (uint32 i = 0; i < tileset_filenames.size(); i++) {
      // Construct the image filename from the tileset filename and create a new vector to use in the LoadMultiImage call
      string image_filename = "img/tilesets/" + tileset_filenames[i] + ".png";
      tileset_images.push_back(vector<StillImage>(TILES_PER_TILESET));

      for (uint32 j = 0; j < TILES_PER_TILESET; j++) {
         tileset_images[i][j].SetDimensions(2.0f, 2.0f);
      }

      if (VideoManager->LoadMultiImage(tileset_images[i], image_filename, 16, 16) == false) {
         cerr << "MAP ERROR: MapMode::_LoadTiles() failed to load tileset image:" << image_filename << endl;
         return;
      }
   }
   // ---------- (3) Read in the map tile indeces from all three tile layers

   // First create the properly sized 2D grid of map tiles, then read the tile indeces from the map file
   for (uint32 r = 0; r < _num_tile_rows; r++) {
      _tile_grid.push_back(vector<MapTile>(_num_tile_cols));
   }

   vector<int32> table_row; // Used to temporarily store a row of integer table data

   // Read the lower_layer
   _map_script.ReadOpenTable("lower_layer");
   for (uint32 r = 0; r < _num_tile_rows; r++) {
      table_row.clear();
      _map_script.ReadIntVector(r, table_row);
      for (uint32 c = 0; c < _num_tile_cols; c++) {
         _tile_grid[r][c].lower_layer = table_row[c];
      }
   }
   _map_script.ReadCloseTable();

   // Read the middle_layer
   _map_script.ReadOpenTable("middle_layer");
   for (uint32 r = 0; r < _num_tile_rows; r++) {
      table_row.clear();
      _map_script.ReadIntVector(r, table_row);
      for (uint32 c = 0; c < _num_tile_cols; c++) {
         _tile_grid[r][c].middle_layer = table_row[c];
      }
   }
   _map_script.ReadCloseTable();

   // Read the upper_layer
   _map_script.ReadOpenTable("upper_layer");
   for (uint32 r = 0; r < _num_tile_rows; r++) {
      table_row.clear();
      _map_script.ReadIntVector(r, table_row);
      for (uint32 c = 0; c < _num_tile_cols; c++) {
         _tile_grid[r][c].upper_layer = table_row[c];
      }
   }
   _map_script.ReadCloseTable();

   // ---------- (4) Determine which tiles in each tileset are referenced in this map
   
   // Set size to be equal to the total number of tiles and initialize all entries to -1 (unreferenced)
   tile_references.assign(tileset_filenames.size() * TILES_PER_TILESET, -1);

   for (uint32 r = 0; r < _num_tile_rows; r++) {
      for (uint32 c = 0; c < _num_tile_cols; c++) {
         if (_tile_grid[r][c].lower_layer >= 0)
            tile_references[_tile_grid[r][c].lower_layer] = 0;
         if (_tile_grid[r][c].middle_layer >= 0)
            tile_references[_tile_grid[r][c].middle_layer] = 0;
         if (_tile_grid[r][c].upper_layer >= 0)
            tile_references[_tile_grid[r][c].upper_layer] = 0;
      }
   }

   // Here, we have to convert the original tile indeces defined in the map file into a new form. The original index
   // indicates the tileset where the tile is used and its location in that tileset. We need to convert those indecs
   // so that they serve as an index to the MapMode::_tile_images vector, where the tile images will soon be stored.

   // Keeps track of the next translated index number to assign
   uint32 next_index = 0;

   for (uint32 i = 0; i < tile_references.size(); i++) {
      if (tile_references[i] >= 0) {
         tile_references[i] = next_index;
         next_index++;
      }
   }

   // Now, go back and re-assign all lower, middle, and upper tile layer indeces with the translated indeces
   for (uint32 r = 0; r < _num_tile_rows; r++) {
      for (uint32 c = 0; c < _num_tile_cols; c++) {
         if (_tile_grid[r][c].lower_layer >= 0)
            _tile_grid[r][c].lower_layer = tile_references[_tile_grid[r][c].lower_layer];
         if (_tile_grid[r][c].middle_layer >= 0)
            _tile_grid[r][c].middle_layer = tile_references[_tile_grid[r][c].middle_layer];
         if (_tile_grid[r][c].upper_layer >= 0)
            _tile_grid[r][c].upper_layer = tile_references[_tile_grid[r][c].upper_layer];
      }
   }

   // ---------- (5) Parse all of the tileset definition files and create any animated tile images that are used
   
   ScriptDescriptor tileset_script; // Used to access the tileset definition file
   vector<uint32> animation_info;   // Temporarily retains the animation data (tile frame indeces and display times)

   for (uint32 i = 0; i < tileset_filenames.size(); i++) {
      if (tileset_script.OpenFile("dat/tilesets/" + tileset_filenames[i] + ".lua", SCRIPT_READ) == false) {
         cerr << "MAP ERROR: In MapMode::_LoadTiles(), the map failed to load because it could not open a tileset definition file: "
            << tileset_script.GetFilename() << endl;
         return;
      }

      tileset_script.ReadOpenTable("animated_tiles");
      for (uint32 j = 0; j < tileset_script.ReadGetTableSize(); j++) {
         animation_info.clear();
         tileset_script.ReadUIntVector(j, animation_info);

         // The index of the first frame in the animation. (i * TILES_PER_TILESET) factors in which tileset the frame comes from
         uint32 first_frame_index = animation_info[0] + (i * TILES_PER_TILESET);

         // Check if this animation is referenced in the map by looking at the first tile frame index. If it is not, continue on to the next animation
         if (tile_references[first_frame_index] == -1) {
            continue;
         }

         AnimatedImage new_animation;
         new_animation.SetDimensions(2.0f, 2.0f);

         // Each pair of entries in the animation info indicate the tile frame index (k) and the time (k+1)
         for (uint32 k = 0; k < animation_info.size(); k += 2) {
            new_animation.AddFrame(tileset_images[i][animation_info[k]], animation_info[k+1]);
         }

         tile_animations.insert(make_pair(first_frame_index, new_animation));
      }
   } // for (uint32 i = 0; i < tileset_filenames.size(); i++)

   // ---------- (6) Add all referenced tiles to the _tile_images vector, in the proper order
   
   for (uint32 i = 0; i < tileset_images.size(); i++) {
      for (uint32 j = 0; j < TILES_PER_TILESET; j++) {
         uint32 reference = (i * TILES_PER_TILESET) + j;

         if (tile_references[reference] >= 0) {
            // Add the tile as a StillImage
            if (tile_animations.find(reference) == tile_animations.end()) {
               _tile_images.push_back(new StillImage(tileset_images[i][j]));
            }

            // Add the tile as an AnimatedImage
            else {
               AnimatedImage* new_animated_tile = new AnimatedImage(tile_animations[reference]);
               _tile_images.push_back(new_animated_tile);
               _animated_tile_images.push_back(new_animated_tile);
            }
         }
      }
   }

   // Remove all tileset images. Any tiles which were not added to _tile_images will no longer exist in memory
   tileset_images.clear();
} // void MapMode::_LoadTiles()
Image
User avatar
gorzuate
Developer
Posts: 2575
Joined: Thu Jun 17, 2004 3:03 am
Location: Hermosa Beach, CA
Contact:

Postby gorzuate » Sun Apr 01, 2007 3:45 am

Nice :)
Image
User avatar
Roots
Dictator
Posts: 8665
Joined: Wed Jun 16, 2004 6:07 pm
Location: Austin TX
Contact:

Re: The Excellent Code Thread

Postby Roots » Thu Sep 11, 2008 11:23 pm

Hey, its been over a year since this thread has seen any posts. :disapprove: Show us the excellent code!
Image
User avatar
Roots
Dictator
Posts: 8665
Joined: Wed Jun 16, 2004 6:07 pm
Location: Austin TX
Contact:

Re: The Excellent Code Thread

Postby Roots » Wed Jul 15, 2009 6:10 am

Last month I finished work on improved collision resolution code for map mode, which turned out to be much more challenging and comprehensive than I originally thought it was. I'll give an overview of it here.

Collision resolution overview
When a sprite collides with something in a map, we have to figure out what to do because the position that the sprite wants to move to is invalid. There are three types of collisions in our design: boundary collisions, map collisions, and object collisions. Boundary collisions are the easiest to handle and occur when the sprite's position exceeds any of the map's boundaries. Map collisions occur when the sprite's collision rectangle overlaps with a tile element of the map that is not walkable, like a wall or building. And object collisions occur when the sprite collides with another map object, which may or may not be another sprite. We also have to take into account the direction that the sprite is trying to move in, specifically we want to try different resolutions for orthogonal and diagonal movement. So the type of collision (three types) and the movement direction of the sprite (two types) give us a total of six resolution cases.

Collision resolution solutions
So what types of solution do we want to offer as a resolution to a collision that occurred? There are several that we perform and we give priorities to some over another. The list includes:
  • Collision alignment: where we align the sprite with what it collided with so they are right next to one another
  • Move around collision corner: for orthogonal movement only, if there is a nearby gap in the other axis we "slide" the sprite around the corner
  • Partial diagonal movement: for diagonal movement only, if we're trying to move a sprite northeast but its blocked by something in either north or east directions, we move the sprite in only the unblocked direction

I give priority to the collision alignment solution in my algorithm. Whenever a collision occurs, first I check if it is aligned with what it collided with and if it is not, I perform the alignment. If it is already aligned, then I try the other collision resolutions. Giving alignment priority eliminates any small "jumps" that you may have seen in previous releases when trying to run into a wall that occur do to our time-based movement system (I won't go into the details about that here).

The Code
Finally the good stuff. :) This is all currently found in src/modes/map/map_objects.cpp. First up is the highest level function where we determine the type of collision that occurred and act accordingly.

Code: Select all

   /** \brief Attempts to modify a sprite's position in response to an obstruction that it has collided with
   *** \param coll_type The type of collision that has occurred
   *** \param coll_obj A pointer to the MapObject that the sprite has collided with, if any
   *** \return True if the sprite's position was successfully modified
   ***
   *** This function enables sprites to "slide" or "roll" around targets that are in their way. For example,
   *** if a sprite moving west ran into a small tree, this function would examine the situation and if appropriate,
   *** it would move the sprite in the north or south directions to get around the tree. This allows for a more
   *** natural movement in the game and also enables sprites to better navigate through narrow passage ways. Put simply,
   *** this function allows sprites to automatically roll/slide around the corners of obstructions.
   ***
   *** If the object that the sprite collided with is anothing moving sprite, then no attempt to modify the sprite's position
   *** is performed. This allows for two moving sprites that collided with one another to not come into a deadlock situation
   *** where they are both trying to move around the other since one sprite will stop its motion and the other will roll
   *** around until the two are free from colliding with one another.
   **/
   bool AdjustSpriteAroundCollision(VirtualSprite* sprite, COLLISION_TYPE coll_type, MapObject* coll_obj);


bool ObjectSupervisor::AdjustSpriteAroundCollision(private_map::VirtualSprite* sprite, COLLISION_TYPE coll_type, MapObject* coll_obj) {
   // 1) Check for special cases where we do not want to adjust the sprite's position even though this function was called
   // If the sprite collided with another sprite that is moving and this sprite is not the map camera (not player-controlled),
   // don't attempt any adjustments. Instead we allow the other sprite to make its own adjustments.
   // TODO: maybe in this case, we should allow for position alignment but no other forms of movement adjustment
   if ((sprite != MapMode::CurrentInstance()->GetCamera()) && (coll_type == OBJECT_COLLISION)) {
      MAP_OBJECT_TYPE obj_type = coll_obj->GetType();
      if ((obj_type == VIRTUAL_TYPE) || (obj_type == SPRITE_TYPE) || (obj_type == ENEMY_TYPE)) {
         VirtualSprite* coll_sprite = dynamic_cast<VirtualSprite*>(coll_obj);
         if (coll_sprite->moving == true) {
            return false;
         }
      }
   }

   // Retrieve collision rectangle of the sprite and the collision object if available
   MapRectangle sprite_coll_rect, object_coll_rect;
   sprite->GetCollisionRectangle(sprite_coll_rect);
   if (coll_obj != NULL) {
      coll_obj->GetCollisionRectangle(object_coll_rect);
   }

   // Attempt alignment and adjustment changes to the sprite as appropriate
   if (sprite->direction & MOVING_ORTHOGONALLY) {
      if (_AlignSpriteWithCollision(sprite, sprite->direction, coll_type, sprite_coll_rect, object_coll_rect) == true) {
         return true;
      }
      else if (coll_type != BOUNDARY_COLLISION) {
         return _MoveSpriteAroundCollisionCorner(sprite, coll_type, sprite_coll_rect, object_coll_rect);
      }
   }
   else { // then (sprite->direction & MOVING_DIAGONALLY)
      return _MoveSpriteAroundCollisionDiagonal(sprite, coll_type, sprite_coll_rect, object_coll_rect);
   }
   return false;
} // bool ObjectSupervisor::AdjustSpriteAroundCollision(private_map::VirtualSprite* sprite, COLLISION_TYPE coll_type, MapObject* coll_obj);


Nothing much to this part. Note that when two moving sprites collide with one another, we only perform collision resolution on one of them and not both.

Now take a look at the collision alignment algorithm. This only performs alignment in an orthogonal direction, though this function is used by the diagonal collision resolution algorithm since it is very rare that we would have a case where we want to align the corner of the sprite with the corner of a collision. Usually we just want to align one side of the sprite's collision rectangle with one side of the collision.

Code: Select all

   /** \brief Attempts to align a sprite's collision rectangle alongside whatever the sprite has collided against
   *** \param sprite The sprite to examine for positional alignment
   *** \param direction The direction in which the alignment should take place (only NORTH, SOUTH, EAST, and WEST are valid values)
   *** \param coll_type The type of collision that occurred
   *** \param sprite_coll_rect The collision rectangle of the sprite
   *** \param object_coll_rect The collision rectangle of the collided object (unused if coll_type is not equal to OBJECT_COLLISION)
   *** \return True if the sprite's position was modified
   **/
   bool _AlignSpriteWithCollision(VirtualSprite* sprite, uint16 direction, COLLISION_TYPE coll_type,
      const MapRectangle& sprite_coll_rect, const MapRectangle& object_coll_rect);


bool ObjectSupervisor::_AlignSpriteWithCollision(VirtualSprite* sprite, uint16 direction, COLLISION_TYPE coll_type,
   const MapRectangle& sprite_coll_rect, const MapRectangle& object_coll_rect)
{
   if ((direction != NORTH) && (direction != SOUTH) && (direction != EAST) && (direction != WEST)) {
      IF_PRINT_WARNING(MAP_DEBUG) << "invalid direction argument: " << direction << endl;
      return false;
   }

   // ---------- (1): Determine the border coordinates that should be examined
   // Used to hold the proper coordinate of the sprite and the collision border
   float pos_sprite = 0.0f, pos_border = 0.0f;

   if (coll_type == BOUNDARY_COLLISION) {
      switch (direction) {
         case NORTH:
            pos_sprite = sprite_coll_rect.top;
            pos_border = 0.0f;
            break;
         case SOUTH:
            pos_sprite = sprite_coll_rect.bottom;
            pos_border = static_cast<float>(_num_grid_rows);
            break;
         case EAST:
            pos_sprite = sprite_coll_rect.right;
            pos_border = static_cast<float>(_num_grid_cols);
            break;
         case WEST:
            pos_sprite = sprite_coll_rect.left;
            pos_border = 0.0f;
            break;
      }
   }
   else if (coll_type == GRID_COLLISION) {
      // When aligning with the grid, we only need to check that the fractional part of the float is equal to 0.0f
      switch (direction) {
         case NORTH:
            pos_sprite = GetFloatFraction(sprite_coll_rect.top);
            pos_border = 0.0f;
            break;
         case SOUTH:
            pos_sprite = 1.0f - GetFloatFraction(sprite_coll_rect.bottom);
            pos_border = 0.0f;
            break;
         case EAST:
            pos_sprite = 1.0f - GetFloatFraction(sprite_coll_rect.right);
            pos_border = 0.0f;
            break;
         case WEST:
            pos_sprite = GetFloatFraction(sprite_coll_rect.left);
            pos_border = 0.0f;
            break;
      }
   }
   else if (coll_type == OBJECT_COLLISION) {
      switch (direction) {
         case NORTH:
            pos_sprite = sprite_coll_rect.top;
            pos_border = object_coll_rect.bottom;
            break;
         case SOUTH:
            pos_sprite = sprite_coll_rect.bottom;
            pos_border = object_coll_rect.top;
            break;
         case EAST:
            pos_sprite = sprite_coll_rect.right;
            pos_border = object_coll_rect.left;
            break;
         case WEST:
            pos_sprite = sprite_coll_rect.left;
            pos_border = object_coll_rect.right;
            break;
      }
   }
   else {
      IF_PRINT_WARNING(MAP_DEBUG) << "invalid collision type: " << coll_type << endl;
      return false;
   }

   // ---------- (2): Check if the sprite is already aligned and modify the sprite's position if it is not
   if (IsFloatEqual(pos_sprite, pos_border, 0.001f) == true) {
      return false;
   }
   else {
      // 0.0005f is subtracted from the distance so that the alignment is never completely perfect. If it was perfect,
      // the alignment would fail because of the collision detection algorithm. For example, if we try to align a sprite
      // moving south with a row of collision grid elements at row 42, if we set the sprite's collision rectangle bottom to
      // 42.0f then the collision detection algorithm will include the collision grid row at 42 in its detection. So instead
      // we set the collision rectangle bottom to something slightly less than 42.0f (~41.9995f) so that this doesn't happen.
      float distance = fabs(pos_border - pos_sprite - 0.0005f);
      return _ModifySpritePosition(sprite, direction, distance);
   }
} // bool _AlignSpriteWithCollision(VirtualSprite* sprite, uint16 direction, COLLISION_TYPE coll_type ... )


Note that we do not check for nor try to perform perfect alignment, but instead leave a really small space between the two alignment objects. Read the comment towards the end of the implementation of that function.

Now here is the code that does the orthogonal collision adjustment to see if we can move around a collision's corner. For example, if the player is moving their sprite to the west and runs into a long wall spanning from north to south, the algorithm will look to the immediate north and immediate south of the sprite to see if there exists a gap large enough that the sprite can squeeze through. If so, then we adjust the sprite's position north or south (depending on where the closest gap is) until the sprite can continue moving west again. This algorithm was actually really fun to work out on paper and then implement. :) :hack:

Code: Select all

   /** \brief A helper function to AdjustSpriteAroundCollision that moves a sprite around a corner
   *** \param sprite The sprite to examine for movement adjustments
   *** \param coll_type The type of collision that occurred (BOUNDARY_COLLISION is an invalid value for this function)
   *** \param sprite_coll_rect The collision rectangle of the sprite
   *** \param object_coll_rect The collision rectangle of the collided object (not valid if coll_type is not equal to OBJECT_COLLISION)
   *** \return True if the sprite's position was modified
   ***
   *** This function is what allows a sprite to "roll" or "slide" around the corner of an obstruction when the sprite moves orthogonally.
   *** The algorithm works by examining the immediate area around the sprite in the direction where the collision
   *** occurred. It will examine a short line in the collision grid immediately next to the sprite in the collision
   *** direction. The length of this line will be three times the length/height of the sprite's collision grid (rounded up to
   *** whole integer values). For example, a sprite moving west with a collision rectangle size of 2 units wide by 3 units high will
   *** equate to a line of 9 collision grid units to examine. If this 9 unit line contains any walkable section
   *** that consists of 3 or more concurrent grid elements, the algorithm instructs the sprite to move in that direction.
   ***
   *** If the collision type was an OBJECT_COLLISION, then in addition to the collision grid the algorithm will examine if there is
   *** a nearby corner of the object that was collided with. However, no other map objects will be considered in this case (because
   *** we wish to limit the computational complexity of this algorithm). If there is another object in the way, then the function will
   *** fail (return false) when it tries to modify the sprite's position around the corner.
   ***
   *** \todo One possible downside to this algorithm is that it doesn't take into account other nearby objects that could be
   *** in the way. Theoretically if we had a line of sprites standing in an open plane and we tried to move one sprite through the middle
   *** of them, the sprite would continue to oscillate around this living wall thinking it has found a gap to get through when
   *** there is none. This is something to consider addressing in the future.
   **/
   bool _MoveSpriteAroundCollisionCorner(VirtualSprite* sprite, COLLISION_TYPE coll_type,
      const MapRectangle& sprite_coll_rect, const MapRectangle& object_coll_rect);


bool ObjectSupervisor::_MoveSpriteAroundCollisionCorner(VirtualSprite* sprite, COLLISION_TYPE coll_type,
   const MapRectangle& sprite_coll_rect, const MapRectangle& object_coll_rect)
{
   // A horizontal adjustment means that the sprite was trying to move vertically and needs to be adjusted horizontally around a collision
   bool horizontal_adjustment = (sprite->direction & (NORTH | SOUTH));
   // Determines if the start or end directions of the grid should be examined in future steps
   bool check_start = true, check_end = true;

   // ---------- (1): If this was an object collision, first check if there is a corner close enough to move around
   if (coll_type == OBJECT_COLLISION) {
      if (horizontal_adjustment == true) {
         if (object_coll_rect.left < sprite_coll_rect.left) {
            check_start = false;
         }
         if (object_coll_rect.right > sprite_coll_rect.right) {
            check_end = false;
         }
      }
      else {
         if (object_coll_rect.top < sprite_coll_rect.top) {
            check_start = false;
         }
         if (object_coll_rect.bottom > sprite_coll_rect.bottom) {
            check_end = false;
         }
      }

      // If the object is big enough that the corners are far away, there's nothing more that can be done
      if ((check_start == false) && (check_end == false)) {
         return false;
      }
   }

   // ---------- (2): Determine the length of the sprite and the start/end points of the collision grid line to examine
   // The length or height of the sprite that determines the dimensions of the line, in collision grid units
   uint16 sprite_length;
   // Stores the col/row endpoints of the collision grid line
   // For horizontal adjustments, start/end represents is left/right directions while vertical adjustments represent top/bottom
   int16 start_point, end_point = 0;

   if (horizontal_adjustment == true) {
      // +1 is added since the cast throws away everything after the decimal and we want a ceiling integer
      sprite_length = 1 + static_cast<uint16>(sprite_coll_rect.right - sprite_coll_rect.left);
      start_point = sprite->x_position - ((3 * sprite_length) / 2);
      end_point = start_point + (3 * sprite_length);

      // Ensure that the line end points do not go outside of the map boundaries.
      start_point = (start_point < 0) ? 0 : start_point;
      end_point = (end_point >= _num_grid_cols) ? _num_grid_cols : end_point;
   }
   else {
      // +1 is added since the cast throws away everything after the decimal and we want a ceiling integer
      sprite_length = 1 + static_cast<uint16>(sprite_coll_rect.bottom - sprite_coll_rect.top);
      start_point = sprite->y_position - (2 * sprite_length);
      end_point = start_point + (3 * sprite_length);

      // Ensure that the line end points do not go outside of the map boundaries.
      start_point = (start_point < 0) ? 0 : start_point;
      end_point = (end_point >= _num_grid_rows) ? _num_grid_rows : end_point;
   }

   // ---------- (3): Determine the collision grid line axis based on the direction the sprite is trying to move
   // Stores the row/col axis of the line
   int16 line_axis = 0;

   switch (sprite->direction) {
      case NORTH:
         // Set to the row above the top of the sprite's collision rectangle
         line_axis = static_cast<int16>(sprite_coll_rect.top) - 1;
         line_axis = (line_axis >= 0) ? line_axis : 0;
         break;
      case SOUTH:
         // Set to the row below the bottom of the sprite's collision rectangle
         line_axis = static_cast<int16>(sprite_coll_rect.bottom) + 1;
         line_axis = (line_axis < _num_grid_rows) ? line_axis : _num_grid_rows - 1;
         break;
      case EAST:
         // Set to the column to the right of the right edge of the sprite's collision rectangle
         line_axis = static_cast<int16>(sprite_coll_rect.right) + 1;
         line_axis = (line_axis < _num_grid_cols) ? line_axis : _num_grid_cols - 1;
         break;
      case WEST:
         // Set to the column to the left of the left edge of the sprite's collision rectangle
         line_axis = static_cast<int16>(sprite_coll_rect.left) - 1;
         line_axis = (line_axis >= 0) ? line_axis : 0;
         break;
   }

   // ---------- (4): Populate the line based upon the collision grid and sprite context information
   // A vector of bools used to represent the collision grid line in front of the sprite that will be examined
   // True values in this vector indicate that the indexed area is not available for the sprite to move to
   // Note that (end_point - start_point) is usually equal to sprite_length * 3, except in some boundary conditions
   // when the grid line is made shorter
   vector<bool> grid_line(end_point - start_point);

   if (horizontal_adjustment == true) {
      for (uint16 i = start_point, j = 0; i <= end_point && i < _collision_grid[line_axis].size(); i++, j++) {
         grid_line[j] = (_collision_grid[line_axis][i] & sprite->context);
      }
   }
   else {
      for (uint16 i = start_point, j = 0; i <= end_point && i < _collision_grid.size(); i++, j++) {
         grid_line[j] = (_collision_grid[i][line_axis] & sprite->context);
      }
   }

   // ---------- (5): Starting from the center, examine both sides of the line for a gap wide enough for the sprite to fit through
   // A counter used for finding a gap of the appropriate size
   uint16 gap_counter = 0;
   // Used to determine how close the nearest available gap is
   int16 start_distance = -1, end_distance = -1;

   // Examine the line segment from the center to the start point
   if (check_start == true) {
      gap_counter = 0;
      for (int16 i = grid_line.size() / 2, j = 0; i >= 0; i--, j++) {
         if (grid_line[i] == true) {
            start_distance = -1;
            gap_counter = 0;
         }
         else {
            if (gap_counter == 0) {
               start_distance = j;
            }
            gap_counter++;
            if (gap_counter == sprite_length) {
               break;
            }
         }
      }
      // If no gap that was large enough was found, the sprite shouldn't adjust itself in the start direction
      if (gap_counter != sprite_length) {
         check_start = false;
      }
   }
   // Examine the line segement from the center to the end point
   if (check_end == true) {
      gap_counter = 0;
      for (int16 i = grid_line.size() / 2, j = 0; i < static_cast<int16>(grid_line.size()); i++, j++) {
         if (grid_line[i] == true) {
            end_distance = -1;
            gap_counter = 0;
         }
         else {
            if (gap_counter == 0) {
               end_distance = j;
            }
            gap_counter++;
            if (gap_counter == sprite_length) {
               break;
            }
         }
      }
      // If no gap that was large enough was found, the sprite shouldn't adjust itself in the start direction
      if (gap_counter != sprite_length) {
         check_end = false;
      }
   }

   // If no gaps were found there's nothing else that can be done here
   if ((check_start == false) && (check_end == false)) {
      return false;
   }

   // ---------- (6): Determine which side has the closest gap for the sprite to go through
   bool move_in_start_direction;

   if ((check_start == true) && (check_end == false)) {
      move_in_start_direction = true;
   }
   else if ((check_start == false) && (check_end == true)) {
      move_in_start_direction = false;
   }
   // In the following cases, both start and end sides are valid to make adjustments to
   else if (coll_type != OBJECT_COLLISION) {
      // Adjust in the position of least grid distance
      move_in_start_direction = (start_distance <= end_distance) ? true : false;
   }
   else {
      // In this case, the collided object must have a collision rectangle that is less than or equal to the width/height of the
      // sprite's collision rectangle. The appropriate sides (left/right or top/bottom) of the object can also not exceed beyond
      // the boundaries of the sprite. So we need to find out which side (start or end) has the most difference between the two
      // objects' edges and move the sprite in the direction of least distance.
      if (horizontal_adjustment == true) {
         move_in_start_direction = ((sprite_coll_rect.right - object_coll_rect.left) < (object_coll_rect.right - sprite_coll_rect.left)) ?
            true : false;
      }
      else {
         move_in_start_direction = ((sprite_coll_rect.bottom - object_coll_rect.top) < (object_coll_rect.bottom - sprite_coll_rect.top)) ?
            true : false;
      }
   }

   // ---------- (7): Adjust the sprite's movement in the appropriate direction
   uint16 direction;
   if (horizontal_adjustment == true) {
      direction = (move_in_start_direction == true) ? WEST : EAST;
   }
   else {
      direction = (move_in_start_direction == true) ? NORTH : SOUTH;
   }

   // Move the sprite in the appropriate direction and reduce the distance moved for this type of movement
   // The reduction of movement distance by sin(45) is the same factor that is used for diagonal movement
   return _ModifySpritePosition(sprite, direction, sprite->CalculateDistanceMoved() * 0.707f);
} // bool ObjectSupervisor::_MoveSpriteAroundCollisionCorner(VirtualSprite* sprite, COLLISION_TYPE coll_type ... )


Pretty crazy isn't it? I construct little segments of the collision grid to examine for a space large enough that the sprite can squeeze through. The gap has to be within the distance of one additional length of the sprite in order for the algorithm to find a valid corner to move around. Going back to the example of a sprite moving west and hitting a wall, this algorithm would check if the sprite could continue moving west ward if the sprite was moved north or south by "one sprite unit". That means, for checking the north direction we move the sprite up such that the original top of their collision rectangle is now the bottom, and likewise for south the original top of the collision rect is now the top of the new position.

This idea of moving around corners was originally created by Drakkoon, so he deserves all the credit for that. But the original implementation of that algorithm wasn't very efficient and became broken sometime later, so I decided to design a more sophisticated one. The concept is really great though, especially for Allacrost. The reason is that it allows us to design narrow passage ways (such as doorways) and not frustrate the hell out of the player by forcing them to try to self-align their sprite so that it fits within the narrow passage.

The final block of code is for diagonal movement. In this case, first we check which of the orthogonal directions (north/south or east/west) that the collision occurred in and check/perform alignment in that direction. Then we try to continue moving the sprite in the non-collision orthogonal direction. So back to our sprite-wall example, if instead the sprite was moving north west and collided with the wall to the west, the sprite would continue moving in the northward direction only until the west direction was no longer blocked. Anyway, here's the code.

Code: Select all

   /** \brief A helper function to AdjustSpriteAroundCollision that handles diagonal adjustment to sprite movement
   *** \param sprite The sprite to examine for movement adjustments
   *** \param coll_type The type of collision that occurred
   *** \param sprite_coll_rect The collision rectangle of the sprite
   *** \param object_coll_rect The collision rectangle of the collided object (not valid if coll_type is not equal to OBJECT_COLLISION)
   *** \return True if the sprite's position was modified
   ***
   *** This algorithm will first check for alignment of the sprite with its collision in either the horizontal or vertical directions
   *** (and in rare cases, both). If the sprite is not aligned with the collision, its position will be adjusted so that it is. If
   *** the sprite is already aligned, then the function will try moving the sprite in only the horizontal or vertical direction.
   *** The sprite will never be positioned to move backwards. That is, if the sprite is trying to move north east, this function may
   *** move the sprite north, east, or northeast, but it will never move it to the south or west.
   **/
   bool _MoveSpriteAroundCollisionDiagonal(VirtualSprite* sprite, COLLISION_TYPE coll_type,
      const MapRectangle& sprite_coll_rect, const MapRectangle& object_coll_rect);


bool ObjectSupervisor::_MoveSpriteAroundCollisionDiagonal(VirtualSprite* sprite, COLLISION_TYPE coll_type,
   const MapRectangle& sprite_coll_rect, const MapRectangle& object_coll_rect)
{
   // Determines the horizontal and vertical directions to examine (north/south and east/west correspond to true/false)
   bool north_or_south = false, east_or_west = false;
   // Determines if horizontal or vertical collision alignment should be performed
   bool check_horizontal_align = false, check_vertical_align = false;

   // ---------- (1): Determine the orthogonal movement directions and reconstruct the sprite's invalid collision rectangle
   switch (sprite->direction) {
      case NE_NORTH:
      case NE_EAST:
         north_or_south = true;
         east_or_west = true;
         break;
      case NW_NORTH:
      case NW_WEST:
         north_or_south = true;
         east_or_west = false;
         break;
      case SE_SOUTH:
      case SE_EAST:
         north_or_south = false;
         east_or_west = true;
         break;
      case SW_SOUTH:
      case SW_WEST:
         north_or_south = false;
         east_or_west = false;
         break;
   }

   // Reconstruct the sprite's collision rectangle at the state when it encountered the collision
   MapRectangle mod_sprite_rect = sprite_coll_rect;
   float distance_moved = sprite->CalculateDistanceMoved();
   if (north_or_south == true) {
      mod_sprite_rect.top -= distance_moved;
      mod_sprite_rect.bottom -= distance_moved;
   }
   else {
      mod_sprite_rect.top += distance_moved;
      mod_sprite_rect.bottom += distance_moved;
   }
   if (east_or_west == true) {
      mod_sprite_rect.left += distance_moved;
      mod_sprite_rect.right += distance_moved;
   }
   else {
      mod_sprite_rect.left -= distance_moved;
      mod_sprite_rect.right -= distance_moved;
   }

   // ---------- (2): Determine whether the collision occurred in the horizontal or vertical direction (or both)
   if (coll_type == BOUNDARY_COLLISION) {
      if (north_or_south == true) {
         check_vertical_align = (mod_sprite_rect.top < 0.0f) ? true : false;
      }
      else {
         check_vertical_align = (mod_sprite_rect.bottom > static_cast<float>(_num_grid_rows)) ? true : false;
      }
      if (sprite->direction == MOVING_EASTWARD) {
         check_horizontal_align = (mod_sprite_rect.right > static_cast<float>(_num_grid_cols)) ? true : false;
      }
      else {
         check_horizontal_align = (mod_sprite_rect.left < 0.0f) ? true : false;
      }
   }
   else if (coll_type == GRID_COLLISION) {
      uint32 axis;

      check_vertical_align = false;
      axis = (north_or_south == true) ? static_cast<uint32>(mod_sprite_rect.top) : static_cast<uint32>(mod_sprite_rect.bottom);
      for (uint32 i = static_cast<uint32>(sprite_coll_rect.left); i <= static_cast<uint32>(sprite_coll_rect.right); i++) {
         if (_collision_grid[axis][i] & sprite->context) {
            check_vertical_align = true;
            break;
         }
      }

      check_horizontal_align = false;
      axis = (east_or_west == true) ? static_cast<uint32>(mod_sprite_rect.right) : static_cast<uint32>(mod_sprite_rect.left);
      for (uint32 i = static_cast<uint32>(sprite_coll_rect.top); i <= static_cast<uint32>(sprite_coll_rect.bottom); i++) {
         if (_collision_grid[i][axis] & sprite->context) {
            check_horizontal_align = true;
            break;
         }
      }
   }
   else if (coll_type == OBJECT_COLLISION) {
      if (north_or_south == true) {
         check_vertical_align = (sprite_coll_rect.top > object_coll_rect.bottom) ? true : false;
      }
      else {
         check_vertical_align = (sprite_coll_rect.bottom < object_coll_rect.top) ? true : false;
      }
      if (east_or_west == true) {
         check_horizontal_align = (sprite_coll_rect.right < object_coll_rect.left) ? true : false;
      }
      else {
         check_horizontal_align = (sprite_coll_rect.left > object_coll_rect.right) ? true : false;
      }
   }

   // ---------- (3): Perform alignments and adjustments in the appropriate directions
   bool vertical_alignment_performed = false, horizontal_alignment_performed = false;
   if (check_vertical_align == true) {
      vertical_alignment_performed = _AlignSpriteWithCollision(sprite, (north_or_south) ? NORTH : SOUTH,
         coll_type, sprite_coll_rect, object_coll_rect);

   }
   if (check_horizontal_align == true) {
      horizontal_alignment_performed = _AlignSpriteWithCollision(sprite, (east_or_west) ? EAST : WEST,
         coll_type, sprite_coll_rect, object_coll_rect);
   }

   // If the sprite's position was changed due to either type of alignment, don't attempt further position changes
   if ((vertical_alignment_performed == true) || (horizontal_alignment_performed == true)) {
      return true;
   }
   // If both types of alignment were checked but no position change was made, the sprite is already aligned and can not be adjusted further
   else if ((check_vertical_align == true) && (check_horizontal_align == true)) {
      return false;
   }
   // If alignment was only checked in one direction but no position changed occurred, try moving the sprite in the non-aligned direction
   else if ((check_vertical_align == false) && (check_horizontal_align == true)) {
      return _ModifySpritePosition(sprite, (north_or_south) ? NORTH : SOUTH, sprite->CalculateDistanceMoved());
   }
   else if ((check_vertical_align == true) && (check_horizontal_align == false)) {
      return _ModifySpritePosition(sprite, (east_or_west) ? EAST : WEST, sprite->CalculateDistanceMoved());
   }
   else { // then ((check_vertical_align == false) && (check_horizontal_align == false))
      // This case should never happen. If it does, the collision detection algorithm may be at fault here.
      IF_PRINT_WARNING(MAP_DEBUG) << "no alignment check was performed against collision in diagonal movement" << endl;
   }
   return false;
} // bool ObjectSupervisor::_MoveSpriteAroundCollisionDiagonal(VirtualSprite* sprite, COLLISION_TYPE coll_type, ... )



From start to finish, this work took me about 3 weeks from design to implementation to testing. It was also very difficult to figure out the best way to organize the code and promote code re-use in these functions, and I kind of ripped things apart a couple times after I realized I was writing the same code in two different places. For a while I considered of doing two-level collision resolutions. For example, a collision occurred, the sprite's position was adjustment, and a different collision occurred as a result of that adjustment, and we try to adjust the sprite a second time to account for the second collision. But I decided against this because I could imagine cases where an infinite loop would occur unless I kept a record of types of collisions, and I decided that just was too much. Another thing the algorithm currently doesn't account for is looking at other objects within the immediate area. The only object the collision resolution code concerns itself with is the object that the sprite collided with (only in the case of object collisions, not the other types of collisions). Examining the position of each object in the immediate area and context of the sprite would require even more work on top of this and I was worried that accounting for this might significantly increase the computational complexity of this algorithm.

When I started on this I didn't expect the amount of code to implement these solutions to be anywhere near this large. In fact during development, a couple of times I questioned if I was really doing this right because there was so much logic to my algorithms. But much of that logic is conditional statements that are executed only in certain cases, so really the code that gets executed when these functions are called are only maybe 1/3 to 1/2 of the amount of code in each function. But overall, I am very satisfied with my work here and I hope that it won't have to be re-visited anytime soon. You may noticed that I was extremely generous in my commenting of this code because of the large amount of logic and cases...it becomes very hard to keep track of it all. Even while I was developing this I had graph paper full of diagrams and notes of the different cases, and I was wondering if there wasn't some way I could add my little illustrations to the comments somehow. :heh: Well, I'm sure this post was more than a mouthful to absorb but hopefully you learned something as a result of me sharing this experience. ;)
Image

Return to “Programming”

Who is online

Users browsing this forum: No registered users and 2 guests