I haven’t written anything on this blog for the past two months. This is partially because I didn’t make time for it and partially because I didn’t have anything interesting to post to the world. I graduated last month and I got a job which is starting in september. It’s a traineeship where I get to work with three local companies, half a year at each. I know some local companies work in java a lot for their tech so I spent two weeks learning it in case it comes up. To learn it I decided I wanted to make something I’m really interested in. So without being too ambitious I decided to write a world simulator.

Sadly I didn’t get to the point of having monsters going around the map destroying towns and adventurers and armies trying to either save people or subjugate them. Nor did I get to the point of having a living economy with a food industry, famines, and farming technology. Neither did I create leaders with a learning AI, reputations and relationships, who decide daily whether to make peace or war. So what did I make? Just some trade route paths, really.

Screenshot showing the city Burmecia with its trade routes and some swimming traders

It may not be the epic I had in my head but I’m still pretty happy with it. The code is available on Github

Note: the jesus-figures walking on water are simply traders without a ship graphic, I wanted to add vehicle art, but didn’t get to it. The lines are trade routes.

Pathfinding

so I’ll talk about how I did pathfinding, the code of which can be found in TradeNode.java.

I was already familiar with A* pathfinding, having used it in some previous projects like Pirate Kingdom, but found this algorithm wasn’t a good match when you wanted to find connections between many cities. Sure, I could have done A* for every city to every other city, but this would be an O(n²) algorithm in this case, which felt bad and unnecessary.

I found the best algorithm for my trade routes would be Dijkstra’s Algorithm, which is similar to the simpler breadth-first search (described here) but allows weighted edges. It expands from a starting tile outwards, always taking the tile that it can reach fastest first. I use it to iterate through tiles and stop it whenever the currently closest tile is beyond our maximum distance. And whenever it passes a tile which is a city, I add it to our TradeNode’s trade routes. Pretty understandable, right? Let’s look at the code.

Implementation

The main pathfinding function is createTradeNetwork, called for each TradeNode after they’ve all been added by the WorldModel. It starts like this:

// uses pathfinding based on Dijkstra's algorithm with a maximum distance
    public void createTradeNetwork() {
        // get rectangle to pathfind in, avoid pathfinding the whole world
        int minX = location.x - maxPossibleTradeDistance();
        minX = (minX < 0) ? 0 : minX;
        int minY = location.y - maxPossibleTradeDistance();
        minY = (minY < 0) ? 0 : minY;
        int maxX = location.x + maxPossibleTradeDistance() + 1;
        maxX = (maxX > world.getWidth()) ? world.getWidth() : maxX;
        int maxY = location.y + maxPossibleTradeDistance() + 1;
        maxY = (maxY > world.getHeight()) ? world.getHeight() : maxY;

To be honest, this was a bit of a premature optimization. As the comment says it creates a rectangle in which we’ll use our pathfinding, so we don’t have to pathfind the whole world. What it doesn’t say is that currently the world is a pretty small place, and the rectangle only a little smaller. I didn’t like the idea of going over the whole world’s tiles, and if I did have a bigger world this would really help, but currently it just makes the code more complicated for not that much gain.

Our pathfinding uses different movement costs for different types of terrain. This is done with a number of constants defined at the start of TradeNode:

    private static final int MAX_TRADE_DISTANCE = 18;
    private static final int LAND_MOVE_COST = 3;
    private static final int WATER_MOVE_COST = 2;
    private static final int CITY_MOVE_COST = 2;
    private static final int SHIP_BOARD_COST = 6;

This means a trader can travel 9 tiles on water(18 / 2) or 6 on land(18 / 3). When moving through a city the movement cost is always 2, this is mostly so moving between close cities over land isn’t so costly (without it I had neighbouring cities prefering to take a boat then take one step over land!). SHIP_BOARD_COST is used whenever a trader goes from land to water or vice versa when there’s no city around. This cost makes it so traders can trade long distances over rivers without being able to go far inland, which creates a more realistic trade area.

The maxPossibleTradeDistance function is made so it returns the largest amount of tiles one can travel in one direction, no matter how these constants are configured:

    // returns maximum possible trade distance in tiles based on constants
    private int maxPossibleTradeDistance() {
        @SuppressWarnings("unused")
        int fastestMoveCost = (WATER_MOVE_COST < LAND_MOVE_COST) ?
            WATER_MOVE_COST : LAND_MOVE_COST;
        fastestMoveCost = (fastestMoveCost < SHIP_BOARD_COST) ?
            fastestMoveCost : SHIP_BOARD_COST;
        fastestMoveCost = (fastestMoveCost < CITY_MOVE_COST) ?
            fastestMoveCost : CITY_MOVE_COST;
        return MAX_TRADE_DISTANCE / fastestMoveCost;
    }

Moving on, all points within our pathfinding rectangle are added to a queue, which is really a set:

        Collection<Point> queue =
            new HashSet<Point>((maxX - minX) * (maxY - minY));

        for (int y = minY; y < maxY; y++) {
            for (int x = minX; x < maxX; x++) {
                Point p = new Point(x, y);
                distances.put(p, Integer.MAX_VALUE);
                queue.add(p);
            }
        }

Here distances is a HashMap that stores the shortest distance we’ve found so far to get to each point. Since we haven’t tried getting to any of these points yet we initialize their distances to the largest integer possible. Next:

        distances.put(null, Integer.MAX_VALUE);
        distances.put(location, 0);

This initializes our own location to have a distance of 0 (since that’s where our trade node is!) and makes it so if distances gets a null it also returns MAX_VALUE.

Now the interesting part begins, the loop itself:

        while (queue.size() > 0) {
            Point p = getMinDistPoint(queue);
            if (distances.get(p) > MAX_TRADE_DISTANCE) {
                break;
            }
            queue.remove(p);

            if (world.getCity(p) != null && !p.equals(location)) {
                tradeRoutes.add(p);
            }

Where getMinDistPoint simply returns the point in the queue with minimal distance using the distance HashMap (by looping through each value in the map). Since we set our location to be 0, and all others to be MAX_VALUE, it will always start with our location.

It checks if the distance is larger than our maximum distance (if so, we should stop pathfinding), and removes the point from the queue. Then it simply checks if there’s a city at the current point, and if there is it will add this point to our list of trade routes. The actual route to get to this point will be possible to find using the nextPoints HashMap that we’ll populate in the following loop. We loop through every neighbouring point around the current point:

            for (Direction d : Direction.values()) {
                Point neighbour = d.move(p);
                if (neighbour.x < minX || neighbour.y < minY ||
                        neighbour.x >= maxX || neighbour.y >= maxY ||
                        // cannot go diagonal on land
                        world.getTerrain(p) && world.getTerrain(neighbour) &&
                        d.isDiagonal()) {
                    continue;
                }
                int dist = distances.get(p) + getMoveCost(p, neighbour);
                if (dist <= MAX_TRADE_DISTANCE &&
                        dist < distances.get(neighbour)) {
                    distances.put(neighbour, dist);
                    nextPoints.put(neighbour, p);
                }
            }
        }

Direction is an enum class containing each cardinal and ordinal direction. d.move(p) returns a point that is point p moved one tile in direction d. We check if the neighbour point is within bounds of our pathfinding rectangle, and if we’re moving land to land we disallow diagonal movement (I did this so ship movement and land movement can’t cross on diagonals, which would be weird).

Then we calculate the distance by getting the movement cost between the current point and the neighbour, and adding this to the distance it took to get to our current point. If this distance is less than the currently fastest distance to get to this point, we update its distance and set its value in nextPoints. This means that for this point (neighbour), the fastest route to get to our TradeNode’s location so far is to go towards point p. Dijkstra’s algorithm works so every point within range of the TradeNode’s location will have a nextPoint, so you can keep iterating on this to get a path from anywhere in range to the TradeNode. See the drawTradeRoutes function below to see how this is used.

In the end we sort all trade routes based on distance, simply to list them more nicely in texts:

Collections.sort(tradeRoutes, (Point p1, Point p2) -> distances.get(p1) - distances.get(p2));

That’s the whole function, now we have all the pathfinding data we need to get from city to city. You can see how pathfinding is actually used by the looking at how they’re drawn in the WorldMap:

    private void drawTradeRoutes(Graphics2D g, TradeNode trade) {
        for (Point tradeRoute : trade.getTradeRoutes()) {
            Point current = tradeRoute;
            while (true) {
                Point next = trade.getNext(current);
                if (next == null) {
                    break;
                }
                drawLine(g, current, next);
                current = next;
            }
        }
    }

Here, getTradeRoutes simply returns the list of trade routes for the trade node, and getNext returns the nextPoint for a given point. Each trade route is a start point, we start drawing lines from there and on each tile we ask the trade route what the best next tile is to get to it in the fastest way, and move to that. If we arrived, the getNext function will return null. You can also see how traders use trade routes in the Trader class.

Discussion and improvement

An obvious improvement to the pathfinding algorithm would be to use a PriorityQueue instead of a HashSet. Java actually has one of these built in. The interface for this class is a bit obnoxious when you want your own compare function though, because it requires a Comparator. So you have to write a whole boilerplate class just to specify a comparison function. It could have been avoided easily if Comparator was a “Functional Interface”. But it’s not because some guy thought it was a good idea to give the Comparator a completely unnecessary equals method next to the compare method. This means you can’t write a lambda function for it. Oh well.

You could probably also avoid the need for the pathfinding rectangle completely by just taking the start point and adding neighbours to the queue if they are in map bounds and within the maximum distance. That’d simplify and make it faster.

Other random things I’ve learned from this mini-project:

  • OpenGameArt is a great place to find art to use in games or simulators. I got the tileset used in the map generator from here and found a lot of other useful stuff.
  • I tried to avoid heavy coupling between my classes in WorldSim and I think I did that pretty well. I avoided inheritance between classes like City and TradeNode, preferring composition and interfaces. I also use an interface to communicate input from WorldMap back to GUI, so WorldMap doesn’t have to depend on the whole of GUI.
  • After adding traders there’s a bit of a lack of abstraction. WorldModel shouldn’t have methods like AddTrader and WorldMap shouldn’t be tasked with drawing every item including cities and traders. If I was going to continue work on this I’d create a Renderable interface that both City and Trader implement, and a AddRenderable method for WorldMap. This would have a render method that allows classes to define their own draw function.
  • I find it a bit funny that even though I didn’t try at all to make this structured like a game, the more stuff I added the more the structure naturally became like a game engine, though with important differences. The main loop is basically the {world.nextTick(); map.updateView();} lambda in GUI.

If you’re interested you’re free to fork or improve WorldSim on Github. I have some ideas on cool stuff to add there as well. Myself, I’m going to work on other stuff. I’ve started on a 13th age web app in golang to help me with my tabletop roleplaying group. Then in september I’ll start getting busy with my new fulltime job. I also want to return to working on the OpenRA map generator so I can finally finish that and get it merged. And with all that I want to keep writing blog entires as well. So I’ll be busy enough.