getCheapestRouteToCluster()

AI discussion, ideas, and SDK help.
Post Reply
User avatar
SunTzu
Lux Cartographer
Posts: 1586
Joined: Sat Jan 14, 2006 1:48 am
Location: Maryland

getCheapestRouteToCluster()

Post by SunTzu » Thu Jul 12, 2007 1:52 am

I tried to modify BoardHelper.cheapestRouteFromOwnerToCont() into a method that looked for the cheapest route to a CountryCluster.

Lux doesn't like my modifications...

Code: Select all

// Get cheapest route from our country to a cluster
public static int[] getCheapestRouteToCluster (int owner, CountryCluster targetCluster, Country[] countries)
	{

	// We keep track of which countries we have already seen (so we don't
	// consider the same country twice). We do it with a boolean array, with
	// a true/false value for each of the countries:
	boolean[] haveSeenAlready = new boolean[countries.length];
	for (int i = 0; i < countries.length; i++)
		{
		haveSeenAlready[i] = false;
		}

	// Create a Q (with a history) to store the country-codes and their cost
	// so far:
	CountryPathStack Q = new CountryPathStack();

	// We explore from all the borders of <cluster>
	int testCode, armiesSoFar;
	int[] testCodeHistory;
	int[] borderCodes = getClusterBorders(targetCluster);
	for (int i = 0; i < borderCodes.length; i++)
		{
		testCode = borderCodes[i];
		armiesSoFar = 0;
		testCodeHistory = new int[1];
		testCodeHistory[0] = testCode;
		haveSeenAlready[testCode] = true;

		Q.pushWithValueAndHistory(
 					countries[borderCodes[i]], 0, testCodeHistory );
		}

	// So now we have all the continent borders in the Q (all with cost 0),
	// expand every possible outward path (in the order of cost).
	// eventually we should find a country owned by <owner>,
	// then we return that path's history
	while ( true )
		{
		armiesSoFar = Q.topValue();
		testCodeHistory = Q.topHistory();
		testCode = Q.pop();

		if ( countries[testCode].getOwner() == owner )
			{
			// we have found the best path. return it
			return testCodeHistory;
			}

		Country[] neighbors = countries[testCode].getAdjoiningList();

		for (int i = 0; i < neighbors.length; i++)
			{
			if ( ! haveSeenAlready[ neighbors[i].getCode() ] )
				{
				// Create the new node's history array. (It is just
				// testCode's history with its CC added at the beginning):
				int[] newHistory = new int[ testCodeHistory.length + 1 ];
				newHistory[0] = neighbors[i].getCode();
				for (int j = 1; j < newHistory.length; j++)
					{
					newHistory[j] = testCodeHistory[j-1];
					}
				Q.pushWithValueAndHistory(
					neighbors[i],
					// If the neighbor is owned by the proper person then minus
					// its armies from the value so if gets pulled off the Q next.
					// Without this there is a bug
					armiesSoFar + (neighbors[i].getOwner() == owner ? -neighbors[i].getArmies() : neighbors[i].getArmies()),
					newHistory );
				haveSeenAlready[ neighbors[i].getCode() ] = true;
				}
			}

		if ( Q.isEmpty() )
			{
			System.out.println(
				"ERROR in cheapestRouteToCluster -> can't pop");
			return null;
			}
		}
	}


// Get array of country codes that are on the border of targetCluster
public static int[] getClusterBorders(CountryCluster targetCluster)
	{
	List clusterCountries = targetCluster.getList();
	Vector list = new Vector();
	for(int i = 0; i <targetCluster> 0)
			{
			list.add(next.getCode());
			}
		}

	// Add to array
	int[] clusterBorders = new int[ list.size() ];
	for (int j=0; j < list.size(); j++)
    	{
    	Integer objectInteger = (Integer) list.get(j);
    	clusterBorders[j] = objectInteger.intValue();
    	}

	return clusterBorders;
	}
Here's the reponse from Lux:
log.txt wrote:There was an error in com.sillysoft.lux.agent.Defender@f1f2cc's placeArmies():
java.lang.NullPointerException
at com.sillysoft.lux.util.CountryStack.topValue(Unknown Source)
at com.sillysoft.lux.agent.Defender.getCheapestRouteToCluster(Defender.java:441)
at com.sillysoft.lux.agent.Defender.getTargetCluster(Defender.java:386)
at com.sillysoft.lux.agent.Defender.placeArmies(Defender.java:121)
at com.sillysoft.lux.B.P(Unknown Source)
at com.sillysoft.lux.B.Z(Unknown Source)
at com.sillysoft.lux.B.P(Unknown Source)
at com.sillysoft.lux.B.run(Unknown Source)
at java.lang.Thread.run(Unknown Source)
I have a feeling that it has to do with the getClusterBorders() method I wrote, but I'm not sure.

Also, the SDK documentation seems a little vague about CountryPathStack... is there a quick and easy explanation?

User avatar
SunTzu
Lux Cartographer
Posts: 1586
Joined: Sat Jan 14, 2006 1:48 am
Location: Maryland

Post by SunTzu » Thu Jul 12, 2007 2:25 pm

I figured out the problem, but I'm still not 100% confident I know what CountryPathStack does.

User avatar
GregM
Luxer
Posts: 252
Joined: Wed Jun 01, 2005 4:33 pm

Post by GregM » Thu Jul 12, 2007 9:12 pm

It's used in all the BoardHelper algorithsm on finding optimal paths. I think what a CountryPathStack does is keep a list of country routes sorted by some value you provide and give you the one sorted first when you ask for it. If you're going to mess around with that code I suggest you study it to understand how the generalized pathfinding algorithm used in BoardHelper works. Like you, I made some custom route-finding functions for BOD, and it took me a while to figure out what was going on there.

Post Reply