screens from python project

Standard

This was potential field project done in python (Numpy, Scipy). Basically generates obstacles. I had a prototype using Python and Ogre to do the actual path finding (https://www.youtube.com/watch?v=jcn6B9Q5_0A). Later on I moved it to c++ (https://www.youtube.com/watch?v=gVB-uGYk50s). (As you may know Potential Field has local optima issues; I was trying to resolve it. You can try to resolving it with some ad-hoc heuristic however there is no 100% sure way).

exactdt_obs

dimple4

base_and_obstacle_combined_03

Project WSS update

Standard

flyingcatstronghold3

I started working on Advertisements. I made a quick prototype with Intel TBB using Advertisements. I ditched MonoGame for Cocos2d. (The reason was I just couldn’t get their asset pipeline to work on Linux; SpriteFont was not working).

I can do a 20HZ update with 1000 entities from server and still run at 60FPS. Albeit now the client is in C++ I’m using native ZMQ messages. I will still have to use produce a protocol over sockets in the future since ZMQ over the internet is not easy to use.

The above screen shows engine room mockup. Eventually part of the game will revolve around building ships and management of engineers (it’s a battlecrusier simulator).

Utility Theory, Needs Based AI and DOT A.I Engine

Standard

I started working project WSS AI and I’ve been researching Utility Theory. I came across Utility Theory in DOT A.I Engine.

What is Utility Theory for games? The idea is to define utility scores from conceptual models of your game world to model decision responses to your game world. This scoring can be applied to individual entities to make decisions or it can be applied to more abstract objects of the game world (A.I director). A soldier entity can use it to decide between taking cover or charging, or a mayor entity can use it to make decisions on how to allocate resources for a city simulation. (Isn’t it cool that this can be used to give VALUE to anything).

At the fundamental level one applies functions to attributes and output them into other functions. By combining these inputs and outputs one can derive a final set of scores. Decisions are based on scores where one can choose a score using max score, random N top scores, or random weighted-value of scores. One can define black boxes where definite world attributes are combined into conceptual attributes (enemy health and strength combined into enemy assessments) and together with other black boxes complex behaviors can result.

Once you learn what patterns and functions (you can be creative with how you come up with your model) you use them to come up with your AI behaviors. It’s really neat. Check out this video from GDC vault to learn all about UT in games:

http://gdcvault.com/play/1015683/Embracing-the-Dark-Art-of

http://gdcvault.com/play/1012410/Improving-AI-Decision-Modeling-Through

One doesn’t need specialized tools to start prototyping A.I with Utility Theory. All you need is python NumPY, SciPY, and graphing (or some other math package like Sage). I did some of this when I was prototyping potential field navigation. You can come up with a model, plug in the numbers, and check it from the resulting graph. This allows you to try out ideas and have quick iteration time without writing a single line of game code. Once you have a prototype you can turn it into c++ game code and have it all work the first time!

Needs Based A.I

This is a method that uses Utility Theory where the world is modeled through advertisements. An advertisement provide benefits or costs which an entity can use to derive a score. One can then combined with some of the utility ideas given in the videos above to complete your A.I.

I guess one could combine this with behavior tree also.

http://www.zubek.net/robert/publications/Needs-based-AI-draft.pdf

DOT A.I Engine:

I’m still checking it out. The version they have right now is pretty cool but is missing a lot of stuff they talk about at various places online. It’s still very cool. Their scoring / attune model is very cool. It uses descriptive statistics together with various mappings for scoring. For example error function F(x) and complement error function F'(x) centered on quantiles of an input relevance function (thus your input can come from arbitrary distributions of values) is used for scoring: where score = F'(currentX) – F(futureX). Score depends on which quantile we center on which affects where the error function is sampled.

I will make more posts when I create prototype models.

 

 

 

Intel TBB Flow graph part 2

Standard

Yesterday I added Intel TBB flow graph to my game as the initial implementation of parallel tasked based pathfinding. My goal for this game is doing things easy but correct from the get-go to support a large set of features in a multiplayer DF clone of sorts–Intel TBB helps with that. (I’m spawning sets of self-contained path solvers using Intel TBB.) Eventually I would like to optimize path finding to achieve not only self-contained path solver but also to accelerate the entire pathing process via nested parallelism.

Intel TBB’s flow graph makes this easy. I accomplish this using 2 function_nodes: a path generator node and a path solver node. Path generator node which is a function of path find request (tuple of id and position) and outputs a Path entity. An edge connects this node to the path solver node. The path solver node is a function of PathEntity and solves a path given id and positions. This node outputs PathEntity into a solved path concurrent_buffer. Since I need to limit the number of entity updates I use another thread (I was unable to find a timer based flow graph node.) which feeds off the solved path concurrent_buffer at a given rate (say 5 times per second) and emits entity state to the network over ZMQ.

Intel TBB makes this easy for I only have to write lambda objects corresponding to the flow graph node. Without it I would have to manually mange the threads (I still have to do this for the timed based entity state emission). Intel TBB also supports concurrent collections which makes my life that much easier. Look how easy the below code is:

// Path generator node. This node will input ID_PATH and generate an path then output it.
	PATH_FIND_NODE pathGenerator(g, flow::unlimited, [&pathEntities](std::tuple<size_t, glm::vec2> pathRequest)->PathEntity* {
		size_t id = std::get<0>(pathRequest);
		pathEntities[id]->position = std::get<1>(pathRequest);
		return pathEntities[id];
	});

	tbb::concurrent_queue<PathEntity*> solvedPathQueue;

	// Path return node. This node will take input ID_PATH and return it to it's corresponding path entity.
	PATH_SOLVE_NODE solvePathNode(g, 50, [&map, &solvedPathQueue](PathEntity* pathEntity)->PathEntity*{
		wss::Path path(MAP_W, MAP_H, map);
		micropather::MicroPather pather(&path);
		std::chrono::steady_clock clock;

		auto start = clock.now();
		size_t stateStart, stateEnd;
		stateStart = wss::Utils::XYToIndex(pathEntity->position.x, pathEntity->position.y, MAP_W);
		stateEnd = wss::Utils::XYToIndex(within(200), within(200), MAP_W );

		int startX,startY,endX,endY;

		wss::Utils::indexToXY(stateStart, MAP_W, startX, startY);
		wss::Utils::indexToXY(stateEnd, MAP_W, endX, endY);

		float cost;
		pathEntity->pathNodes->clear();
		pather.Solve((void*)stateStart, (void*)stateEnd, pathEntity->pathNodes, &cost);
		pathEntity->traversing.store(true);
		solvedPathQueue.push(pathEntity);
		//cout << "solvedPathQueue pushed! " << pathEntity->id << endl;
		std::chrono::duration<double> elapsed = clock.now() - start;
		//cout << "Path solver elasped time: " << elapsed.count() * 1000.0 << endl;

		return pathEntity;
	});

void regionDataPublisher(zmqpp::socket &publisher, PATH_FIND_NODE &pathFindNode, tbb::concurrent_queue<PathEntity*> &solvedPathQueue, tbb::concurrent_vector<Entity*> entities) {
	using namespace std;

	std::chrono::steady_clock clock;

	// Initialize path.
	for (auto entity : entities) {
		pathFindNode.try_put(std::tuple<size_t, glm::vec2>(entity->id, entity->position));
	}

	while (1) {
		auto start = clock.now();

		// Grab a bunch fo path
		{
			//size_t size = entities.size();
			for (size_t i = 0; i < 200; ++i) {
				PathEntity* pathEntity;
				if (solvedPathQueue.try_pop(pathEntity)) {
					entities[pathEntity->id]->pathNodes = pathEntity->pathNodes;
					entities[pathEntity->id]->currentNode = 0;
				}
			}
		}

		// Traverse nodes
		{
			for (auto entity : entities) {
				if (entity->pathNodes != 0) {
					if (entity->currentNode < entity->pathNodes->size()) {
						size_t currentIndex = (size_t)(*entity->pathNodes)[entity->currentNode++];
						//wss::Utils::indexToXY(currentIndex, MAP_W, entity->position);
						wss::Utils::indexToXY(currentIndex, MAP_W, entity->position);
					}
					else {
						entity->pathNodes = 0;
						pathFindNode.try_put(std::tuple<size_t, glm::vec2>(entity->id, entity->position));
					}
				}
			}
		}
... WRITES OUT ZMQ ...

	}
}

dfd

Intel tbb flow graph

Standard

I refactored my game jam to use Intel TBB flow graphs. It made the code cleaner and MUCH faster.

I can run path finding (this is pathfinding without optimization) on 950 entities with an server update rate of 5 times per second.

I will discuss this in more depth tomorrow since I”m kind of tired right now.

https://github.com/beyzend/wss/blob/9d0a8c7ad58a0a3d03ec403168a3956f069b645a/wss/gameserver/src/wssserver.cpp

flyingorcstronghold

Specifically this is the flow graph for path finding:

// Path generator node. This node will input ID_PATH and generate an path then output it.
	PATH_FIND_NODE pathGenerator(g, 100, [=](PathEntity* pathEntity)-&gt;PathEntity* {
		return pathEntity;
	});

	std::vector&lt;size_t&gt; map;

	for (size_t y = 0; y &lt; MAP_H; ++y) {
		for (size_t x = 0; x &lt; MAP_W; ++x) {
			map.push_back(1);
		}
	}



	// Path return node. This node will take input ID_PATH and return it to it's corresponding path entity.
	PATH_FIND_NODE returnPathNode(g, 20, [&amp;map](PathEntity* pathEntity)-&gt;PathEntity*{
		wss::Path path(MAP_W, MAP_H, map);
		micropather::MicroPather pather(&amp;path);
		//cout &lt;&lt; &quot;solving path for id: &quot; &lt;&lt; pathEntity-&gt;id &lt;&lt; endl;
		std::chrono::steady_clock clock;
		auto start = clock.now();
		size_t stateStart, stateEnd;
		//cout &lt;&lt; &quot;path start: &quot; &lt;&lt; pathEntity-&gt;position.x &lt;&lt; &quot;, &quot; &lt;&lt; pathEntity-&gt;position.y &lt;&lt; endl;
		stateStart = wss::Utils::XYToIndex(pathEntity-&gt;position.x, pathEntity-&gt;position.y, MAP_W);
		stateEnd = wss::Utils::XYToIndex(30 + within(50), 30 + within(40), MAP_W);

		size_t startX,startY,endX,endY;

		wss::Utils::indexToXY(stateStart, MAP_W, startX, startY);
		wss::Utils::indexToXY(stateEnd, MAP_W, endX, endY);

		//cout &lt;&lt; &quot;startI: &quot; &lt;&lt; startX &lt;&lt; &quot;, &quot; &lt;&lt; startY &lt;&lt; endl;
		//cout &lt;&lt; &quot;endI: &quot; &lt;&lt; endX &lt;&lt; &quot;, &quot; &lt;&lt; endY &lt;&lt; endl;


		float cost;
		pathEntity-&gt;pathNodes-&gt;clear();
		pather.Solve((void*)stateStart, (void*)stateEnd, pathEntity-&gt;pathNodes, &amp;cost);
		pathEntity-&gt;traversing.store(true);
		std::chrono::duration&lt;double&gt; elapsed = clock.now() - start;
		//cout &lt;&lt; &quot;Path solver elasped time: &quot; &lt;&lt; elapsed.count() * 1000.0 &lt;&lt; endl;
		return pathEntity;
	});

AI path finding

Standard

https://github.com/beyzend/wss/blob/2165359872e4d396e6f9f8579a0127b2efdb5e33/wss/gameserver/src/wssserver.cpp

I worked on my little JAM some more. I implemented AI path finding in a thread. The thread process PathEntities (completely separate from entities that is processed in another thread) at some rate. Once it finds a path it notifies the entity in another thread (this currently is done through a mutex lock on the entities) and gives the found path. The other thread processes it’s own entities and checks to see if it has a path, if it has a path it will traverse it. This thread ticks at 1.0/5 seconds and sends out message at that rate.

The client receives position updates at the above rate of 1 position update per 1.0/5.0 seconds. The client can attach it’self to any entity on the server and updates the camera accordingly.

Currently at this tick rate of 5 per second I can support 280 entities. As I increase the number of entities supported on the server the network gets overwhelmed and some entities does not get updated (or could be some bug).

I will probably not support this many entities at once anyway. It’s a little game jam which I plan to build into a full fledged game later on (everything C++ and UDP).

(Note: it’s still preliminary. I have not implemented fixed tick rate properly yet).

(Note: I want to use tasked based threading later).