Hexagon and HexagonGrid suggestions

[Zervox]

I'd like to suggest to make Hexagon use std::array instead of vector(avoid dynamic creation of data) since neighbors is always 6.
Hexagon would be represented like this
std::array<Hexagon*,6> &neighbors();
in Hexagon::Hexagon() functions

Hexagon::Hexagon()
Hexagon::Hexagon(unsigned int number)
{
	for (int i = 0; i < _neighbors.size(); i++) {
		_neighbors[i] = nullptr;
	}
}

HexagonGrid::HexagonGrid()

std::array<Hexagon*, 6 > &neighbour= hexagon->neighbors();
			
			if (index1 < _hexagons.size()) neighbour[0] = _hexagons.at(index1).get();
			if (index2 < _hexagons.size()) neighbour[1] = _hexagons.at(index2).get();
			if (index3 < _hexagons.size()) neighbour[2] = _hexagons.at(index3).get();
			if (index4 < _hexagons.size()) neighbour[3] = _hexagons.at(index4).get();
			if (index5 < _hexagons.size()) neighbour[4] = _hexagons.at(index5).get();
			if (index6 < _hexagons.size()) neighbour[5] = _hexagons.at(index6).get();

I also rewrote the the findPath as in this case dynamic data creation might actually be useful as double arrays of 200*200 which in almost all cases of the game you would still only get an array length of 15 at most.

std::vector<Hexagon*> HexagonGrid::findPath(Hexagon* from, Hexagon* to)
	{
		Hexagon* current = nullptr;
		std::vector<Hexagon*> result;
		std::priority_queue<Hexagon*, std::vector<Hexagon*>, HeuristicComparison> unvisited;
		std::map<unsigned int,unsigned int> cameFrom;
		std::map<unsigned int, unsigned int> costSoFar;

		// if we can't go to the location
		// @todo remove when path will have lenght restriction
		if (!to->canWalkThru()) return result;

		unvisited.push(from);

		cameFrom.insert(std::make_pair(from->number(), 0));
		costSoFar.insert(std::make_pair(from->number(), 0));


		while (!unvisited.empty())
		{
			current = unvisited.top(); unvisited.pop();
			if (current == to) break;
			// search limit
			if (costSoFar.at(current->number()) >= 100) break;
			std::array<Hexagon*, 6 > &neighbor = current->neighbors();
			for(int i=0; i<6; i++)
			{
				if (neighbor[i] != nullptr) {
					if (!neighbor[i]->canWalkThru()) continue;

					unsigned int newCost = costSoFar.at(current->number()) + 1;
					costSoFar.insert(std::make_pair(neighbor[i]->number(), 0));
					auto &heighborCost = costSoFar.at(neighbor[i]->number());
					if (heighborCost == 0 || newCost < heighborCost)
					{
						// add hexagon to unvisited queue only once and don't change heuristic
						if (heighborCost == 0)
						{
							neighbor[i]->setHeuristic(distance(neighbor[i], to) + newCost);
							unvisited.push(neighbor[i]);
						}
						heighborCost = newCost;
						cameFrom.insert(std::make_pair(neighbor[i]->number(), current->number()));
					}
				}
			}
		}

		// found nothing
		if (current != to) return result;


		while (current->number() != from->number())
		{
			result.push_back(current);
			current = _hexagons.at(cameFrom[current->number()]).get();
		}

		return result;
	}

[phobos2077]

@Zervox: Please create pull request instead. It is hard to see the actual changed code this way.

PS: I agree about using array for neighbors. Need to study your pathing changes in more details later, because I don't want to break this function again and spent hours debugging much later :)

[Zervox]

sorry had to recreate fork as I had changed a vast majority of the files from another experiment.
pull request made

[alexeevdv]

@Zervox why you closed this issue? Seems like good suggestion for HexagonGrid refactoring

[speIIbound]

The performance of falltergeist is fairly bad, at 640x480 resolution I'm getting anywhere between 30-60 frames (mostly on the lower end), especially when I move the mouse around there's lots of stuttering. I went ahead and used perf record on linux and the function with the most overhead at 2.80% is Falltergeist::HexagonGrid::hexagonAt()

The code for this function is, as of now:

Hexagon* HexagonGrid::hexagonAt(const Point& pos) { for (auto& hexagon : _hexagons) { auto hexPos = hexagon->position(); if (pos.x() >= hexPos.x() - HEX_WIDTH && pos.x() < hexPos.x() + HEX_WIDTH && pos.y() >= hexPos.y() - 8 && pos.y() < hexPos.y() + 4) { return hexagon.get(); } } return nullptr; }

So, Everytime we move the mouse pointer the engine iterates through the entire HexagonGrid of the map looking for the Hexagon under the pointer.

Some ideas I had to improve this performance and remove the stuttering

1. Splitting the hexagonGrid up into quadrants or sections
   When you scroll map position the game will test to see which sections are in view currently and store this in a vector. Rather than searching through the entire hexagongrid of this map, it will only search through the currently visible sections of the HexagonGrid.

2. A delay to search for the hexagon under the pointer
   consider if we move the mouse pointer only a pixel away on accident, the game then will iterate through the entire HexagonGrid once again looking for the hexagon one pixel over the next gameloop. Instead of doing this perhaps wait 100 ms or 200 ms. so if we are running a smooth 60 fps a delay of 100 ms would be a check every 6 frames, and 200 ms would be a check every 12 frames. I don't think this delay would be very noticeable to the player and would likely remove the currently noticeable stutter

3. Some sort of asynchronous interruptible search in another thread
   Consider we move mouse pointer a pixel over, in another thread a search begins for this hexagon, but midsearch we move the mouse again a pixel over. The search is then ended midsearch and we begin again searching for the new position.

Anyway I don't know if any of this is feasible and I haven't looked entirely into how the pathfinding system currently works. I'm just throwing ideas out there and I'm not the best programmer, I haven't written code in quite a while. I don't know where else to write this, there's no forum or any active places to discuss this engine

[FakelsHub]

Yes, in the engine a lot of things need to rewrite, remove unnecessary checking, such as vector.at(), in general, all that unnecessarily affect performance.