Civil Nations (Civilization mechanics): Border algorithm?

Warning: wall of text.

tl;dr: I'm a relative n00b at programming and I'm looking for advice on creating borders.

My minecraft server is the "official" server for civfanatics.com, a fansites of civilization games. I thought it would be fitting to try and bring some of the core game concept into minecraft. The first problem I want to tackle is borders, and I am not exactly sure the best way to proceed.

For those who are not familiar with Civ III-V, the borders of your nation expand as cities develop, adding more tiles into your empire. I want to try to emulate this and I have two ideas how to do it, but I am not sure which is best for performance.So I am asking those who have a lot more experience in programming than me

My first thought was using simple circles that expand as the town develops. This would end up being a lot like Rise of Nations. Problems happen when borders of different civs meet and I'm not sure how RoN did it. I figure I could use a 'culture strength' variable that diminishes with distance, and the border is where the variables of the two borders are equal. I'm not sure how to store this sort of border information though for quick lookup, otherwise this would be very expensive to compute for every person for every move event. I'm hoping someone has a good idea how to do this in a sane and efficient manner.

My backup thought is to create a 2d array of tiles, similar to what Towny does. Civs deposit culture points into the tiles around them, and the civ with the most points in that tile owns it. This seems to have a lot of room for optimization and is a fair enough approximation, even though I prefer the first option.

 

There is an interesting mathematical property that if you use the square of the distance as a measure, it causes the borders between towns to be straight lines (if they intersect)

Each city/town would have a culture score that gives a radius.

The strength of the town's influence at point a point is

(City radius squared) - (distance from town centre to player squared)

If a player is 100 blocks from the centre and the town has a radius of 50, then that gives a score of

(50*50) - (100*100) = -7500

This means that the player is outside the circle.

Likewise, if the player is 40 blocks away, the score is

(50*50) - (40*40) = +900

and so the player is inside the circle.

Thus the formula gives a circle when towns don't overlap. The rule is that the player is inside the border of the town with the highest influence, but only if that town has a positive influence.

However, when they do overlap, the border will be a straight line between the 2 towns.

I would suggest
- give each town an ID number
- create a HashMap which maps Chunks to LinkedList
- The linked lists will store all towns near the Chunk

(probably went a little overboard here Also it may not compile, but should be reasonable).

You need to update the cache any time you update the towns. Otherwise, it just pulls the precomputed results from the cache.

Code:

HashMap<Chunk,LinkedList<Integer>> nearbyTowns = new HashMap<Chunk,LinkedList<Integer>>();

HashMap<String,Integer> townIds = new HashMap<String,Integer>();
HashMap<Integer,Location> townLocations = new HashMap<Integer,Location>();
HashMap<Integer,Integer> townRadius = new HashMap<Integer,Integer>();

int nextId = 1;

boolean addTown(String name, Location loc, Integer radius) {
    
    if(townIds.containsKey(name)) {
        return false; // town already exists
    }

    townIds.put(name,nextId);
    townLocations.put(nextId,loc);
    townRadius.put(nextId,radius);

    return true;
}

// returns 0 if unowned, otherwise town ID

Integer findOwner(Location loc) {
    Integer bestTown = 0;
    Integer bestInfluence = 0;

    int cx = loc.getBlockX() >> 4;
    int cz = loc.getBlockY() >> 4;

    Chunk chunk = new Chunk(cx,cz);

    LinkedList<Integer> towns = nearbyTowns.get(chunk);

    if( towns==null) return 0;

    Iterator<Integer> itr = towns.iterator();

    int px = loc.getBlockX();
    int pz = loc.getBlockZ();

    while( itr.hasNext() ) {
        Integer current = itr.next();

        int townX = townLocations.get(current).getBlockX();
        int townZ = townLocations.get(current).getBlockZ();

        int townR = townRadius.get(current);

        int dx = townX - px;
        int dz = townZ - pz;

        int influence = (townR)*(townR) - (dx*dx + dz*dz);

        if( influence > bestInfluence ) {
            bestInfluence = influence;
            bestTown = current;
        }

    }

    return best;
}

boolean updateCache() {

    nearbyTowns = new HashMap<Chunk,LinkedList<Integer>>();
    
    boolean first = true;
    int minx;
    int maxx;
    int minz;
    int maxz;

    Iterator<Integer> itr = townIds.values.iterator;

    // find the rectangle that includes all towns

    while(itr.hasNext()) {
        Integer current = itr.next();

        Location loc = townLocations.get(current);
        int bx = loc.getBlockX();
        int bz = loc.getBlockZ();

        int r = townRadius.get(current);

        int cx = bx>>4; // convert to chunk coords
        int cz = bz>>4;
        int cr = (r>>4) + 1;

        if( first || cx + cr > maxx ) maxx = cx + cr;
        if( first || cx - cr < minx ) minx = cx - cr;
        if( first || cz + cr > maxz ) maxz = cz + cr;
        if( first || cz - cr < minz ) minz = cz - cr;

        first = false;
    }

    for( int cx = minx; cx <= maxx; cx ++ ) {
        for( int cz = minz; cz <= maxz; cz ++ ) {
            Chunk chunk = new Chunk( cx , cz );
            Location loc = new Location();
            loc.setX(cx<<4);
            loc.setZ(cz<<4);
            nearbyTowns.put( chunk , findNearbyTowns(loc) );
        }
    }

}

LinkedList<Integer> findNearbyTowns(Location loc) {

    LinkedList<Integer> towns = new LinkedList<Integer>();

    int px = loc.getBlockX();
    int pz = loc.getBlockZ();

    Iterator<Integer> itr = townIds.values.iterator;

    while(itr.hasNext()) {
        Integer current = itr.next();

        int townX = townLocations.get(current).getBlockX();
        int townZ = townLocations.get(current).getBlockZ();

        int townR = townRadius.get(current);

        int dx = townX - px;
        int dz = townZ - pz;

        int influence = (townR)*(townR) - (dx*dx + dz*dz);

        if( influence > 0 ) {
            towns.add(current);
        }

    }
    return towns;
}

 

Thank you! It never even crossed my mind to use chunks in assisting the lookups. I was also considering using something like f(x)=n/1.1^(x-m) and define the boundary where f(x) = 1. Your method is much better. Thank you very much!

Now for my next challenge, learning SQL. Maybe I'll cheat and just use yaml dumps....

 

This is super cool I used to spend all my time since I was about 12 playing Civ (every version...), until I stumbled upon minecraft. I would really like to help make this happen.

 

This plugin might do what you are looking for. You would have to change the radius with growth, etc.
http://forums.bukkit.org/threads/interesting-places-name-areas-in-the-world.1463/page-2