Algorithmically Placing Towers

Monday August 19, 2013 | by IncaWarrior

Map Additions Feature

One fun feature in the Populous Matchmaker is the option to automatically add features to a map. While training huts and normal huts are semi-randomly placed, towers have a more complicated algorithm so they are placed in useful locations. Since towers give FireWarriors a larger range the higher they are, the ideal locations are on the highest ground. Many levels include small hills or cliffs designed for towers, so those are the target locations.

Scouting out the area

As an example, let’s place towers for the Blue tribe on the popular map Face Off:

Blue’s base is on the left.

The towers obviously should be in the player’s base, so that’s the starting point for available spots:

The first obvious spots to remove are those in the ocean, and those within the Reincarnation Site of the Shaman:

The next filter is to look only at those spots that are on high ground. There’s a fairly low bar for this, but it cuts out a lot of options:

A closer look at the land

With this smaller set of spaces, it’s time to look more closely at the squares themselves. Towers need a relatively flat square to be built on, and there needs to be an adjacent square on the side of the door for followers to enter.

The squares that are too steep can be removed:

Now all the remaining spots are viable for placing a tower on that will be accessible by followers. There are a lot of spots in the middle areas that shouldn’t be considered. The most strategic placements for towers are those on a hill or cliff edge so these final spots will have to be looked at more closely.

It’s a little hard to visualize, but the different sized squares are drawn around the tower spots looking for one where two sides of the square are lower elevation than the tower in question. This seems to work for most situations. The spaces that can’t have a square drawn around them with two sides at a lower elevation are discarded:

Shamans and Angles

One final filter is to look at the locations of the other players. There shouldn’t be a tower placed in an enemy base for obvious reasons, so any tower closer to another shaman than to the one we’re making towers for is removed. In the level Face Off, it looks like there are none that fit that description:

The set of spaces remaining would all be fairly good places, but which one is the best? Now is the time to start looking at the angles of the towers and the higher elevations. Since the Reincarnation Site of the shaman is essentially the center of the base, all threats come towards that - hence the towers should be facing away from the Reincarnation site. This is relatively easy to do since towers can only face four directions, so the map can just be split into quadrants that meet at the Shaman:

With just a few spots in an area, each one is assigned a score for how good it is. Higher elevation adds to the score, as does proper orientation. Towers that cannot be placed with proper orientation (i.e. there isn’t room to place the entry on flat ground behind it) have a lowered score depending on the angle.

The final spots are selected in order of which has the highest score. The spots surrounding a selected tower are removed, so only the best of a cluster of towers will be picked:

Finally, the actual tower objects are added to the map with the appropriate orientation:

The same process is run for the other tribes, and the rest of the map objects are made visible:

The map data is then saved to the level folder and the players are ready to go!

Hosting For All

Thursday February 28, 2013 | by IncaWarrior

Matchmaker 1.7.2.0+ allows almost all to host

Matchmaker 1.7.2.0 introduces a new way for networking Populous. Instead of relying on the aging network code of Populous designed for 90’s style Internet connections, Populous now relays all traffic through the matchmaker. This allows the matchmaker to control essentially every aspect of networking meaning easier host setup with fewer firewall rules and a lot less unexplained connection problems.

Issues are still being worked out, so if you try to host a game and it gives an error or doesn’t work, contact IncaWarrior for instructions on sending some logs so it can be worked out. Apart from the hosting/network improvements, this solution also opens the doors for a number of other interesting features, so stay tuned!