I wrote a post on implementing a simple A* Pathfinding algorithm a couple months ago. When I went to add it to my game I ran into some interesting differences I wanted to write an update on.

Here is the algorithm working on my game server. Both player and NPC are red blocks. When the player is within viewable range of the NPC, the NPC will start chasing it.

The pathfinding algorithm allows the NPC to maneuver around blocked tiles.

Coordinate to Tile Mapping

One thing I discovered while incorporating it into my game was my simple example had a 1:1 coordinates to tile ratio. Coordinates 0,0 was the first tile, and 0,1 was the second tile. When tiles were 16×16 pixels, the coordinate to index mapping broke.

To address this, I needed to pass  map width and map height in tiles, as well as the tile size so it was known when a new row started and the bounds of the map.

I did this by creating a map struct that contained the width, height, size, and pointer to the tile vector.

struct GameMap {
	GameMap() {}
	GameMap(int _map_width, int _map_height, int _tile_size, std::vector<unsigned int>* _tiles) : map_width(_map_width), map_height(_map_height), tile_size(_tile_size), tiles(_tiles) {}
	int map_width = 0;
	int map_height = 0;
	int tile_size = 0;
	std::vector<unsigned int>* tiles;
};

Getting the mapping information into the pathfinder class was a small challenge due to circular dependencies between my GameState class and GameMob (GameState already include GameMob). A forward declaration can be used to address this, but I decided I would split out the Map into its own code unit (different cpp file).

The pathfinding functions were altered to take the map width and height (in tiles, not pixels) and the tile size.

AStarPathFinding::AStarPathFinding(int _map_width, int _map_height, int _tile_size,  std::vector<unsigned int>* _tiles) {
	this->_map_tile_width = _map_width;
	this->_map_tile_height = _map_height;
	this->_tile_size = _tile_size;

	for (int i = 0; i < _tiles->size(); ++i) {
		Point current_point = index_to_coords(this->_map_tile_width, this->_tile_size, i);
		Node* node = new Node(current_point.x, current_point.y, _tiles->at(i) == 1, 0, coords_to_index(this->_map_tile_width, this->_tile_size, current_point.x, current_point.y));
		this->_grid.push_back(node);
	}
}

int coords_to_index(int tiles_per_row, int tile_size, int x, int y) {
	int index = floor(x / tile_size);
	index += (floor(y / tile_size) * tiles_per_row);
	return index;
	//return (y * tile_size) + (x);
}

Point index_to_coords(int tiles_per_row, int tile_size, int index) {
	Point p;
	p.y = tile_size * floor(index / tiles_per_row);
	p.x = tile_size * (index - (floor(index / tiles_per_row) * tiles_per_row));
	return p;
}

coords_to_index and index_to_coords only needs the tiles per row (map width) in order to know when a tile drops to a new row.

Coding Aggro

The NPC engaging the player is outside of the pathfinding algorithm. It uses a very rudimentary raycasting algorithm (if it can be called that) that only looks up, down, left, and right.

bool GameMob::_raycastTiles(GameMap map, GameUnit* source, GameUnit* target, int distance) {
	// Is within view distance (ignoring any visual blockers)
	int x = target->positionX - source->positionX;
	int y = target->positionY - source->positionY;

	if (sqrt(x*x + y * y) > distance) {
		return false;
	}

	// Is there anything blocking line of sight?
	int start_tile = coords_to_index(map.map_width, map.tile_size, source->positionX, source->positionY);
	int target_tile = coords_to_index(map.map_width, map.tile_size, target->positionX, target->positionY);
	int view_x;
	int view_y;
	int tile_view_distance = floor(distance / map.tile_size);

	// Check up
	for (int i = 0; i < tile_view_distance; ++i) {
		int new_tile = start_tile - (i * map.map_width);
		if (new_tile < 0) {
			continue;
		}

		if (map.tiles->at(new_tile) == 1) {
			break;
		}

		if (new_tile == target_tile) {
			return true;
		}
	}

	// Check down
	for (int i = 0; i < tile_view_distance; ++i) {
		int new_tile = start_tile + (i * map.map_width);
		if (new_tile > map.map_height) {
			continue;
		}

		if (map.tiles->at(new_tile) == 1) {
			break;
		}

		if (new_tile == target_tile) {
			return true;
		}
	}

	// Check left
	for (int i = 0; i < tile_view_distance; ++i) {
		int new_tile = start_tile - i;
		if (new_tile < 0) {
			continue;
		}

		if (map.tiles->at(new_tile) == 1) {
			break;
		}

		if (new_tile == target_tile) {
			return true;
		}
	}

	// Check right
	for (int i = 0; i < tile_view_distance; ++i) {
		int new_tile = start_tile + i;
		if (new_tile > map.map_width) {
			continue;
		}

		if (map.tiles->at(new_tile) == 1) {
			break;
		}

		if (new_tile == target_tile) {
			return true;
		}
	}
}

This can be improved by only looking int the direction the player is and only checking tiles that are in that line of sight.

Moving Forward

One thing I realized from this implementation is the pathfinding quickly became proprietary to tile based maps. I would like to generalize it and just make it coordinates.

I ran into some bugs early on when the NPC wasn’t standing precisely on a tile. I think moving to coordinates would help here.

I would also like to move to interpolating the movement between coordinates so it is more precise.