[Imek]

Hey,

I'm currently programming a game in Java with the JMonkey engine - a 3D space combat game - and I'm quite interested in AI, so I wanted to do some kind of learning system. I had the idea of having factions maintain spatial memory of where they last saw ships - over time, they would estimate where a ship they saw a while ago might be (based on its last seen speed and direction, maximum speed...) by giving each area in space a probability and a danger rating and so on. This info could be used to plot safe paths for trading, plan patrol routes, and such. The specifics of this aren't at concern here (though if you have comments I would still like to hear them) - what I'm worried about is that my implementation might not be the best. Here is the essence of the problem:

public class SectorGraph
{
	/*
	 * The world graph, containing knowledge and estimations of ship locations. Because 
	 * coordinates could be positive or negative, we split this up into  eight different 
	 * ArrayLists for each side of each axis' origin a point could be on. Each world node
	 * is a cube defined by its minimum position (and a constant size, see Globals class)
	 * Each of these spaces is split into an arraylist for each dimension, so for example
	 * to look up WorldNode 3, -63, 109 we would do: PosNegPosNodes.get(3).get(62).get(108).
	 */ 
	private ArrayList<ArrayList<ArrayList<WorldNode>>> PosPosPosNodes;
	private ArrayList<ArrayList<ArrayList<WorldNode>>> PosPosNegNodes;
	private ArrayList<ArrayList<ArrayList<WorldNode>>> PosNegPosNodes;
	private ArrayList<ArrayList<ArrayList<WorldNode>>> PosNegNegNodes;
	private ArrayList<ArrayList<ArrayList<WorldNode>>> NegPosPosNodes;
	private ArrayList<ArrayList<ArrayList<WorldNode>>> NegPosNegNodes;
	private ArrayList<ArrayList<ArrayList<WorldNode>>> NegNegPosNodes;
	private ArrayList<ArrayList<ArrayList<WorldNode>>> NegNegNegNodes;

New ArrayLists are created and inserted on demand. This all seems a bit messy, but I can't think of a better way to do it with the possibility of positions going off infinitely in any direction. I have three values that can be changed to make it more efficient: a maximum lifetime for a WorldNode before it is cleaned up, and a time period between updates of the graph, and a size for each world node (cube side length).

However, it does seem like there's still going to be a lot of time jumping through lists and filling lists with nulls (for example if we insert a fresh node at (0, 1000, 1000) and there's nothing around it, we need to insert a lot of ArrayLists just to get there). I first thought of just having a list of nodes, but that seemed like it would get even worse with having to step through a very long list.

Any comments or suggestions regarding this? Would perhaps some kind of Map that maps a coordinate to a world node possibly be better? Any ideas would be great.

Thanks,

-Joe

[baavgai]

That make my brain hurt just looking at it.

I'd use a single list and let the equality of objects do the work. Make x,y,z the key. Like so:

import java.util.*;

public class SectorGraph {
	
	private class WorldNode {
		public int x,y,z;
		public Object worldData = null;
		public WorldNode(int x, int y, int z) {
			this.x = x;
			this.y = y;
			this.z = z;
		}
		public WorldNode(int x, int y, int z, Object worldData) {
			this(x,y,z);
			this.worldData = worldData;
		}
		
		public boolean isEmpty() { return this.worldData == null; }
		
		// for lookup
		public String toString() { return "(" + this.x + "," + this.y + "," + this.z + ")"; }
		public int hashCode() { return this.toString().hashCode(); }
		public boolean equals(Object obj) {
			if (obj==null) { return false; }
			if (this.getClass().isInstance(obj)) {
				return this.hashCode()==obj.hashCode();
			}
			return false;
		}
	}
	
	private List<WorldNode> worldNodes = new ArrayList<WorldNode>();
	
	public WorldNode getNode(int x, int y, int z) {
		WorldNode searchNode = new WorldNode(x, y, z);
		int index = worldNodes.indexOf(searchNode);
		if (index!=-1) {
			searchNode = worldNodes.get(index);
		}
		return searchNode;
	}
	
	public void setNode(WorldNode node) {
		int index = worldNodes.indexOf(node);
		if (worldNodes.indexOf(node)!=-1) {
			worldNodes.remove(index);
		}
		if (!node.isEmpty()) {
			worldNodes.add(node);
		}
	}

	public void setNode(int x, int y, int z, Object worldData) {
		setNode(new WorldNode(x, y, z, worldData));
	}
}

Hope this helps.

This post has been edited by baavgai: 07 January 2008 - 01:45 PM

[Imek]

Wouldn't that mean that, once my list got really big, it would have to go through a lot of nodes to search for my provided one? This is why I was trying to come up with something that provided more "direct" access to elements.

Come to think of it, that solution may still be better despite that. Do you think a HashMap could possibly be faster if it got really big?

[baavgai]

I understand, you're trying to get the most speed.

There are a few things here. One, the list removes or ignores a Node when it's empty, which should help. But the big thing is we're not reinventing the wheel. We trust that in the guts of Java, the List<> implementations have been reasonably optimized.

You got me curious, so I decided to test this.

import java.util.*;
//import java.util.Random;

public class ListTest {
	private Random rnd = new Random();
	
	private class TestNode {
		public String key;
		public Object someValue = null;
		public TestNode(String key) {
			this.key = key;
			this.someValue = key;
		}
		public TestNode(String key, Object someValue) {
			this.key = key;
			this.someValue = someValue;
		}
		// for lookup
		public String toString() { 
			return key 
				+ " = " + ((this.someValue==null) ? "NULL" : this.someValue.toString()); 
		}
		public int hashCode() { return this.key.hashCode(); }
		public boolean equals(Object obj) {
			if (obj==null) { return false; }
			if (this.getClass().isInstance(obj)) {
				return this.hashCode()==obj.hashCode();
			}
			return false;
		}
	}
	
	private TestNode createRandomNode() {
		return new TestNode("(" + rnd.nextInt(10000) + "," + rnd.nextInt(10000) + ")");
	}

	private TestNode getRandomNode(List<TestNode> list) {
		int index = rnd.nextInt(list.size());
		return list.get(index);
	}
	
	private void fillList(List<TestNode> list, int size) {
		for(int i=0; i<size; i++) {
			list.add(this.createRandomNode());
		}
	}
	
	private long seekTest(List<TestNode> list) {
		TestNode node = getRandomNode(list);
		//System.out.println(node);
		long startTime = new Date().getTime();
		list.contains(node);
		long endTime = new Date().getTime();
		long timeTaken = endTime - startTime;
		return timeTaken;
	}
	
	private void testList(List<TestNode> list, int size, int testCount) {
		//System.out.println("Filling list: " + size);
		list.clear();
		fillList(list, size);
		long totalTime = 0;
		for(int i=0; i<testCount; i++) {
			long timeTaken = seekTest(list);
			System.out.println("Seek time (ms): " + timeTaken);
			totalTime += timeTaken;
		}
		System.out.println("Average seek time (ms): " + (totalTime/testCount));
	}
	
	public static void Test() {
		int size = 100000;
		int testCount = 10;
		ListTest lt = new ListTest();
		System.out.println("ArrayList");
		lt.testList(new ArrayList<TestNode>(), size, testCount);
		System.out.println("LinkedList");
		lt.testList(new LinkedList<TestNode>(), size, testCount);
	}
}

So, with a list of 100000 items, on my woefully underpowered (by today's standards) 2.4GHz and 1GB RAM box, I got the following results.

ArrayList
Seek time (ms): 30
Seek time (ms): 11
Seek time (ms): 1
Seek time (ms): 12
Seek time (ms): 5
Seek time (ms): 12
Seek time (ms): 6
Seek time (ms): 11
Seek time (ms): 2
Seek time (ms): 3
Average seek time (ms): 9
LinkedList
Seek time (ms): 10
Seek time (ms): 15
Seek time (ms): 10
Seek time (ms): 5
Seek time (ms): 17
Seek time (ms): 21
Seek time (ms): 7
Seek time (ms): 3
Seek time (ms): 12
Seek time (ms): 17
Average seek time (ms): 11

About 10 milliseconds for 100000 objects? Not bad at all, I think.

You could probably squeeze a little more out of it if you implemented Comparable and used a tree of some sort. The reason this is fast is that it uses the hashValue internally for indexing. In Java, each object must implement hashValue and equals, so if we override those, we can be sure all the basic list functions will work as we expect.

Even if you think you can roll a better one yourself, you'll still probably want something like a List<> interface to make accessing nodes easier.

Hope this helps.

[Imek]

Thanks for this - I realised that this graph would only need updating periodically, and that it could be done in a separate thread, so even if so many milliseconds were to impact frame rate it won't be a huge issue to fix. There are a few other ways I thought of to improve performance if necessary, but I'm kind of short on time and just want to get something basic done, so this should do great for now.