Jump to content

  • Log In with Google      Sign In   
  • Create Account

EWClay's Journal

Command queues

Posted by , 28 March 2013 - - - - - - · 948 views

Squad movement is looking ok now.

Given solid pathfinding code and physics, it was already working reasonably well in that units could simply push other units out of the way to get where they wanted to go. It just didn't look that good. I chose a simple solution; as my squads are quite small I don't need anything too sophisticated.

First I predict collisions using a circle intersection test. I only care about the next predicted collision. The unit's path is deflected either left or right depending on which requires the least deflection while still leaving room to pass. Once the collision is no longer predicted, the unit returns to the original path. It's nice because it's sort of self-correcting, and doesn't involve modifying the path or the path-following code.

With that working I could move on to commands. I currently have three: move, follow and attack. Because I'm using a component system, each command is a component. Follow and attack both make use of move. It's possible to use these components directly, but I wanted to have a queuing system for setting up waypoints and general automation. How to handle that? Another component of course! The command queue sends messages to the other components to begin and end actions, they carry out the action and respond with success or failure messages.

For the commands in the queue I use a Command base class with virtual functions. This makes it easy to plug in new commands. But most of the work is done in the components.

This could get interesting if I start mixing it with AI. How much intelligence should an individual unit have? I want some of them to not even have the pathfinding component, so they could only follow or attack within line of sight. My attack command is very basic at the moment. It could take into account cover, different weapon types and the current health of the unit.

Next, though, I think I really need to make a proper level. It's just been small test areas so far and they don't have enough scope to try out these ideas properly. So I shall put on another hat and become a level designer for a bit.

More pathfinding

Posted by , 21 March 2013 - - - - - - · 580 views

Squad movement is giving me a bit of trouble.

I've got it working fine for one unit, but I want to select several units together and have them move as a group, without getting in each other's way. My first thought was to pick the closest unit to the destination, make that the leader, and have the others follow. This works, but it's not the best formation tactically as only the first unit can attack anything in front. Also, it doesn't work with command queues: I might tell four units to move but one is busy doing something else and needs to follow later, at which point I have no knowledge of which units were selected together. Anyway, even if the units were not selected together, they still need to play nicely and not cause jams.

My current plan then, is a localised avoidance system whereby any unit can plot a path around nearby obstacles in a cooperative way. But I still have to work out exactly how to do that.

Immediate mode GUI

Posted by , 18 March 2013 - - - - - - · 1,334 views

My GUI is sort of done. Well, code is never really finished, but it's functional and I'm looking at other things now.


As it's almost stand-alone, I'm releasing the source too:


It requires Visual Studio 2012 with the November 2012 compiler and Allegro 5. Only the x64 build is working.

There's other stuff in there too. I'll talk about that when I have time to document it.

A-star pathfinding

Posted by , 17 March 2013 - - - - - - · 1,210 views

Here's an implementation of A* in C++ which hopefully works and is quite sensible.

Note that
  • It doesn't use a million templates, or any for that matter (except std containers).
  • It doesn't do stupid things like trying to erase out of the middle of a queue.
  • It assumes nothing about data structures so is highly generic.
  • It doesn't come with its own memory allocator/hash table/queue/linked list. It's just A*.
Instructions: derive from it and implement the virtual functions. Then call FindPath(start, end). That's it!
class AStar
	void FindPath(int startIndex, int endIndex)
		// Add the nodes in the starting zone to the open list.
		std::vector<int> connectedNodes;
		GetConnectedNodes(startIndex, connectedNodes);

		for (int nodeIndex : connectedNodes)
			float f = GetDistance(startIndex, nodeIndex) + GetDistance(endIndex, nodeIndex);
			openQueue.emplace(OpenQueue::value_type(-f, nodeIndex));
			nodeMap[nodeIndex] = NodeInfo(f, startIndex, GetData(startIndex));

		while (!openQueue.empty())
			// Get the first item in the queue and remove it.
			float currentLength = -openQueue.top().first;
			int currentIndex = openQueue.top().second;

			// Add it to the closed list;
			std::pair<ClosedSet::iterator, bool> r = closedSet.insert(currentIndex);

			if (r.second == true) // If it was already on the closed list, ignore it.
				if (currentIndex == endIndex) // Found the final node.
					int nodeIndex = currentIndex;

					// Output the path.
					while (true)

						if (nodeIndex == startIndex)

						nodeIndex = nodeMap[nodeIndex].parentNode;


				GetConnectedNodes(currentIndex, connectedNodes);

				float g = currentLength - GetDistance(currentIndex, endIndex);

				for (int newNodeIndex : connectedNodes)
					if (closedSet.find(newNodeIndex) == closedSet.end())
						float f = g + GetDistance(currentIndex, newNodeIndex) 
									+ GetDistance(newNodeIndex, endIndex);

						auto it = nodeMap.find(newNodeIndex);

						if (it == nodeMap.end() || it->second.f > f)
							// The node may be in the open set already. If so, this will add it again
							// with a lower f score and update the NodeMap.
							openQueue.push(OpenQueue::value_type(-f, newNodeIndex));
							nodeMap[newNodeIndex] = NodeInfo(f, currentIndex, GetData(currentIndex));


	struct NodeInfo
		NodeInfo() {}
		NodeInfo(float f, int parentNode, int data) : f(f), parentNode(parentNode), data(data) {}

		float f;
		int parentNode;
		int data;

	virtual void GetConnectedNodes(int nodeIndex, std::vector<int>& nodes) = 0;
	virtual float GetDistance(int node1, int node2) = 0;
	virtual void AddToPath(int nodeIndex) = 0;
	virtual int GetData(int nodeIndex) = 0;

	typedef std::priority_queue<std::pair<float, int>> OpenQueue;
	typedef std::unordered_set<int> ClosedSet;
	typedef std::unordered_map<int, NodeInfo> NodeMap;

	OpenQueue openQueue;
	ClosedSet closedSet;
	NodeMap nodeMap;

March 2013 »


Recent Entries

Recent Comments