DESIGN: Barbarian placement

[J Bytheway]

I've been researching the way the location of barbarian spawns is chosen.

The way this is performed is really bizarre (and I found at least two bugs in the code ).

If there is exactly one human player, then they are placed as follows (I call this the SP algorithm):

A human city is selected at random, and then neighbours of this are selected at random repeatedly (essentially this generates a random walk around the map) for at most 4000 steps until it finds a land square not visible to the human player which is at least as far from the nearest human city as a given minimum distance, and then places the barbs there.

If there are zero or more than one human players, then they are placed as follows (I call this the MP algorithm):

Random squares on the map are chosen (for at most 400 attempts) until a land square is found which no player can see, and the barbs are placed there.

There are several problems with the SP algorithm:

Barbs will always be placed "just out of sight" for the human player, and whether other players can see the square is ignored (although this is a bug - it isn't supposed to be ignored). This is very unfair, and strange.

This method is likely to produce barbs on the borders between the human player and the AIs, exactly in the warzones where all the troops will be and so the barbs will probably be easily dealt with.

If that doesn't happen, then they will be placed just inside the neigbouring AI civs, possibly right next to their cities (in fact, it might try to place them inside their cities!) which is also not good.

The way in which the code randomly walks around in the SP algorithm is quite silly, and could easily result in it getting stuck and no barbs being produced when a large portion of the map is visible to the human player. This is particularly true on a map with much water.

Because of these problems, I suggest we strip out the SP algorithm and use the MP algorithm for all games - it seems sensible. It's implementation could probably be improved, but it's sufficient for the moment.

Some people have put forward more suggestions for barbarian camps, etc., but for the moment I'm primarily interested in what we should do in the short term.

[J Bytheway]

Blast! Wrong forum...

Ah... Right forum. Thanks very much .

[Ekmek]

Originally posted by The Big Mc
I have just drafted an idea for a much more complicated barbarian model.

Four types of barbarians creation types

Random

Barbarians appear randomly on the map

Regional
A region is specified which has a lot of barbarians often being only 5 or 6 tiles big.

Leader

A random barbarian leader is generated which changes with age.

Camp

A barbarian camp works similar to the leader


The hard bit is going to be to get the barbarian unit DB to add and remove units depending on age

There will also be an option to allow you to attack barbarian leaders and camps to steel gold of the barbarians.

is there a way to implement BigMCs model (without too much work?)

[J Bytheway]

Originally posted by E
is there a way to implement BigMCs model (without too much work?)

Well...

Originally posted by The Big Mc
Random

Barbarians appear randomly on the map

Well, obviously this is easy, because it already exists.

Regional
A region is specified which has a lot of barbarians often being only 5 or 6 tiles big.

This is not so easy. How do you choose the region? What if it turns out to be a small island - then that island will be swarming with barbs when someone finds it. What happens when this region is built over by a player?

Leader

A random barbarian leader is generated which changes with age.

Camp

A barbarian camp works similar to the leader

This should be relatively easy, but I don't really understand the purpose. I think the way the game chooses which units to spawn for the barbs is somewhat silly anyway, and should probably be altered...

The hard bit is going to be to get the barbarian unit DB to add and remove units depending on age

...using age to decide what units to use is another way, but I still don't think it's right.

At present any land unit with a non-zero attack value can appear, and which one does is chosen at random from the top few units available to any player (sorted by attack value). It seems to me that it might make more sense to, for example, allow units.txt to specify which units can be barbs, and prehaps sort by the sum of attack and defense, rather than just attack.

There will also be an option to allow you to attack barbarian leaders and camps to steel gold of the barbarians.

This would probably be most easily done with SLIC...

[Ekmek]

Ok then I'll go with the MP fix and just have SLIC for the niceties,

but I think have a standard list of what barbs appear during different ages should be in the main game, not just a modified unit.txt I dont want to see barbarian tanks or something just warriors, gerrillas, horseman

[Tamerlin]

The MP algorithm appears better than the SP one. Though I am against Barbarians camps, at least the way they are implemented in Civ3 (I am mostly against all things inspired from Civ3 actually) I think that Barbarians should sometimes (not always) be allowed to create a new AI civ when they manage to take a City from a player and to keep it for a while.

[Unspeakable Horror]

This is not so easy. How do you choose the region? What if it turns out to be a small island - then that island will be swarming with barbs when someone finds it.

What´s so bad about it? Imagine they are very agressive natives
It would be nice to have some opposition to settle on the island, for example in my current game I have a big island just in front of my own, it would be natural to have some population that got away from my empire (criminals, smugglers?) in a place where law that´s not exists

What happens when this region is built over by a player?

Err? What do you mean? When the player borders extends over the island?
Well, I don´t know

[Solver]

MP algorithm seems better.

As for other ideas... nothing wrong with lots of Barbs on an isle! As it is, I can feel pretty secure colonizing an island and only sending one all-around good unit, like Cavalry there. Ideally, I'd also like to see Barbarians tougher, with better units in later ages (terrorists, sorta), and the ability to spawn unconventional units. For instance, Barb Slavers could stand for some small roaming slaver groups that don't care whom they enslave.

[Flinx]

Re: DESIGN: Barbarian placement

I've been researching the way the location of barbarian spawns is chosen.
The way this is performed is really bizarre (and I found at least two bugs in the code ).
If there is exactly one human player, then they are placed as follows (I call this the SP algorithm):
A human city is selected at random, and then neighbours of this are selected at random repeatedly (essentially this generates a random walk around the map) for at most 4000 steps until it finds a land square not visible to the human player which is at least as far from the nearest human city as a given minimum distance, and then places the barbs there.

IIRC the minimum distance is from the text files and varies/can vary with barbarian difficulty.

If there are zero or more than one human players, then they are placed as follows (I call this the MP algorithm):
Random squares on the map are chosen (for at most 400 attempts) until a land square is found which no player can see, and the barbs are placed there.
There are several problems with the SP algorithm:
Barbs will always be placed "just out of sight" for the human player, and whether other players can see the square is ignored (although this is a bug - it isn't supposed to be ignored). This is very unfair, and strange.

I do not view the preferential placement of the random barbarians near human players as a problem. The AI knows not to walk through goody huts which spawn barbarians, so the preferential placement can be thought of as the same thing. Conceptually, barbarians should not appear within the vision of any military unit (AI or Human).

This method is likely to produce barbs on the borders between the human player and the AIs, exactly in the warzones where all the troops will be and so the barbs will probably be easily dealt with.
If that doesn't happen, then they will be placed just inside the neigbouring AI civs, possibly right next to their cities (in fact, it might try to place them inside their cities!) which is also not good.

The no-man’s-land between civs is conceptually where I would most likely expect to find barbarians, provided that there is no military unit to see them appear, other than another barbarian.

The way in which the code randomly walks around in the SP algorithm is quite silly, and could easily result in it getting stuck and no barbs being produced when a large portion of the map is visible to the human player. This is particularly true on a map with much water.

The random walk around does seem somewhat non-optimal. Having the number of barbarians that appear decrease as the map (land tiles) becomes increasingly visible to everyone makes sense to me. The MP algorithm achieves this by requiring the tile be not currently visible to any player (AI or Human) and so is no different than the SP algorithm in this respect.

Because of these problems, I suggest we strip out the SP algorithm and use the MP algorithm for all games - it seems sensible. It's implementation could probably be improved, but it's sufficient for the moment.
Some people have put forward more suggestions for barbarian camps, etc., but for the moment I'm primarily interested in what we should do in the short term.

I think we should come up with a new algorithm for placing barbarians. With one human player, I think the AIs may be worse off by switching to the MP algorithm.

[The Big Mc]

Well I have been working hard on this planning at the moment.

What we could do id multiples of these as apposed to just one barbarian algorithm.

For example an option to add algorithms to deal with barbarian camps could be that the camp take could gain things that the barb took

E.g. money slaves or pw



Oh and to answer the question

What happens when this region is built over by a player?

The barbarian’s spawn chance goes down by 10% for every tile making the barbarian chance 10% when you take all tiles (based on a 9 tile region).

[J Bytheway]

Originally posted by Flinx
IIRC the minimum distance is from the text files and varies/can vary with barbarian difficulty.

Yes, that's where the value comes from.

I do not view the preferential placement of the random barbarians near human players as a problem.

Perhaps not. It goes against my grain to be biased in this way, but it might give better gameplay, provided the other problems are dealt with.

The random walk around does seem somewhat non-optimal. Having the number of barbarians that appear decrease as the map (land tiles) becomes increasingly visible to everyone makes sense to me. The MP algorithm achieves this by requiring the tile be not currently visible to any player (AI or Human) and so is no different than the SP algorithm in this respect.

Well, it is different in that it is likely to place barbs if there is non-visible land anywhere, rather than just near the human player, and it is more likely to find somewhere to put the barbs - it will have a 50% chance when less than 0.2% of the map is unseen land - this might in itself become a problem because the barbs will become denser and denser as the amount of unseen land decreases.

I think we should come up with a new algorithm for placing barbarians.

I can't think of a good one...

With one human player, I think the AIs may be worse off by switching to the MP algorithm.

I'm not so sure - in the buggy SP algorithm they might get barbs on their very doorstep once the human civ borders theirs. Certainly in the early game the AIs will be worse off, but once most of the land is covered in cities it depends how densely the AIs units/cities are packed compared to the human, and thus how much unseen land there is in or near their civ...

[star mouse]

Re: DESIGN: Barbarian placement

Originally posted by J Bytheway Because of these problems, I suggest we strip out the SP algorithm and use the MP algorithm for all games - it seems sensible. It's implementation could probably be improved, but it's sufficient for the moment.

To spawn barbarians, we should use the MP code always.

We can also do barbarians in the following manner:

1. Count how many tiles on the map are outside all player's fog of war. (Could take a while? If it does then we should not use this method).
2. If no tiles are outside the fog of war for every player, then stop here (because we cannot spawn barbaraians).
3. Randomly choose one of these tiles and place the barbarians there. The number of barbarians to place is inversely proportional to the number of tiles where the barbarians can be spawned.

So if there's a lot of free space on the map, we spawn a few barbarians, but if there's just a few tiles we spawn a horde.

[star mouse]

Re: DESIGN: Barbarian placement

Originally posted by J Bytheway
I've been researching the way the location of barbarian spawns is chosen.

The way this is performed is really bizarre (and I found at least two bugs in the code ).

If there is exactly one human player, then they are placed as follows (I call this the SP algorithm):

A human city is selected at random, and then neighbours of this are selected at random repeatedly (essentially this generates a random walk around the map) for at most 4000 steps until it finds a land square not visible to the human player which is at least as far from the nearest human city as a given minimum distance, and then places the barbs there.

If for some reason you wanted to keep the SP algorithm, you could improve it by doing the following:
1. Select a city at random. (Could be a human city or an AI city)
2. Select a random direction (360 degrees).
3. Move in that direction, and use Bresenham's algorithm to choose the squares.
4. Stop when you find a square outside the view of all empires. Place the barbarians there.
5. If you go right around the map in either direction, then stop.

The random walk is eliminated.

[J Bytheway]

For the record, as per popular request, I've implemented the change I first suggested (source here).

This change is in the newest playtest, so feel free to test and comment .

[Ekmek]

J bytheway,

Did this code at new Unit Flags that prevented some units being used as barbarians...just checking...

if(rec->GetCantBuild())
			continue;

		if(!rec->GetMovementTypeLand())
			continue;
		
		if(rec->GetAttack() < 1)
			continue;

		if(g_exclusions && g_exclusions->IsUnitExcluded(i))
			continue;
	
		
		

		if(SomeoneCanHave(rec)) {
			for(j = 0; j < num_best_units; j++) {
				if(rec->GetAttack() > best[j].attack) {
					for(k = num_best_units - 1; k >= j+1; k--) {
						best[k] = best[k-1];
					}
					best[j].index = i;
					best[j].attack = (sint32)rec->GetAttack();
					count++;
					break;