More on navier-stokes

Standard

Okay just to let people know that I’m only slightly crazy (perhaps a lot of foolishness and silliness). I’ve been looking at a lot of physics lately (you know just to make sure I don’t lose my math skills) and because it’s one of my interests. I’m no physicist nor am I really that great at math but it’s tickles my interest in the same way that doing game development and learning graphics algorithm does for me. Anyway so I started looking at solar power stuff and also at sonoluminescence (cavitation) which is what I have been reading up on in the past couple of months (along side the usual programming stuff). Sonoluminescene is really interesting because I think it’s one of those things that’s on the edge of the really small and kinda small. A lot of interesting stuff goes on there I think. Like it’s where microfludic (streamers), colloid, interfaces, fluid dynamics, and molecular dynamics all meet. I’m no expert it’s just so damn cool.

Doing all that I got really interested in complex analysis again (remembering how some things are just so darn easy in that space). Especially Mobius transformation and along with all the group theory stuff that goes with that. For example infinite composition of analytic functions. Another thing is inversions (like circles at infinity with infinite curvature and how it relates to the picture of limits and the infinitesimal; inverting infinities and stuff; continuous transformations and exponential maps). I keep on thinking there may be ways to use that for simulations, and also N-body problems. (I have this idea I want to check out involving N bodies). And also I keep on imagine that one could use this (plus maybe knot theory) to solve certain graph problems. I just seem to think there is a connection. Basically I want to work towards checking out some of these ideas I have.  Yes all these ties back into the sonoluminescene thing.

There are also things I want to learn/know more about regarding Quantum Mechanics. I mean I get the general gist of how it’s supposed to work. My question is if I’m an ant sitting on a quantum particle am I uncertain about my own momentum and where I’m supposed to go? (ok I realize I may not really understand QM). Why probabilities? I understand that it’s probability amplitude (unitary) and the wave function. I just want to check it out myself I guess. For example the quantum potential. Could it be… Anyway when and as I continue to learn it I hope it will be all be satisfactorily explained at least in my own head.

Yes it ties back to fluid dynamics also. Turbulence for example. Divergence etc. Like at the finest level you may conserve energy but what if you take larger and larger steps (grids on top of your finest level; see how this may be related to turbulence, local time, initial conditions, sources and sinks, global effect, etc). Circles at infinity.

I’m no expert I just like to learn about these things and think stupid thoughts on them. It’s fun.

Lastly I have not forgotten my game projects. All this ties back to the dwarf fortress clone (kinda) I was making. It’s my project hey I get to put whatever I think is cool in it :). But a long time ago I wanted to make a game called Fluid Dynamics Asteroid. No I have not forgotten about that one

 

 

 

 

 

 

 

 

 

 

 

Navier-Stokes existence and smootheness

Standard

I think there may be a way to solve Navier-Stokes existence and smoothness problem! Am I crazy? Probably.

The trick is to figure out if it becomes non-deterministic given some initial input v(0). At the same time proving it will be smooth. The energy E will blow up given it’s randomness. It is supposed to be deterministic (may be chaotic) at each time step but if it’s non-deterministic it will blow the fuck up!

Yes there may be a way to show that. Go read Terrence Tao’s blog on it.

I think I may be crazy tho. LoL.

Yes there may be a way to make it NOT blow up by doing “surgery” to FIX THE THING. How would you know where the singular points are and when they happen? There may be a way dude. THERE MAY BE A WAY! There may be a way to do fluid simulations, or perhaps N body systems using this method. You may be able to say something about Quantum systems also.

May also have something to say about certain GRAPH problems. Say what dude? ARE YOU CRAZY!

HEY but hmmm right maybe NOT you know. Why wouldn’t you like? To everything turn turn turn, to everything turn turn turn.

 

 

 

 

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