Announcement

**Locutus** · May 28, 2003, 12:13

Nope, I don't think so

**Immortal Wombat** · May 28, 2003, 13:08

Unless you can get the IsContinentBiggerThan function to work properly, and your map doesn't have two continents of identical sizes on it.
Probably you could do it the long way, checking each route manually...

**Locutus** · May 28, 2003, 14:13

You can write a function yourself. I was working on this myself but other affairs have been keeping me busy.

The idea is simple: at the start of the game, cycle through the entire map from top-left to bottom-right, row-by-row, and assign a continent ID to every tile. For each tile, check if the tiles above it and left of it happen to be of the same type (where valid types are land and water) and if so, copy their ID. If not, assign a new, unique ID to this tile. Give land continents positive values as ID and 'water continents' negative ones, so that you can easily determine the difference between bodies of water and bodies of land (you may not have an immediate use for it now, but you might in the future).

If several neighbouring tiles are of the same type but have different IDs, then two parts of the same continent were apparently seperated by water (or land, if it's a body of water) and incorrectly got different IDs. So then cycle through the part of the map you already finished again and replace obsolete IDs with the correct ones (e.g. if continent 3 and continent 5 turn out to be the same continent, replace all 5s with 3s (or vice versa)).

The only problem with this code could be that it might add a lot of workload: you'll be doing a *lot* of calls to TerrainType and CreateLocation functions, which may slow down the game quite a bit. Of course, the good thing is that you only have to do this once per game (or rather, once per /reloadslic), after that you can store the 'continent map' and write your own functions to take advantage of it (in case of checking if 2 things are on the same continent, simply check the continent IDs of their tile).
I was actually thinking of combining this continent mapping with other mappings, such a threat mapping and desire mapping, but that's still in the brainstorm phase. It could make it more interesting though: 1 slowdown at the start of the game would give you a whole set of mappings to write AI code on for the rest of the game, without considerable delays (hopefully).

There are a couple of issues I was still working out, but those are details. I probably won't get around to writing this before the end of June, so if you're in a hurry feel free to implement this algorithm in SLIC yourself.

Here's some pseudocode to represent the above (can't guarantee this is functional, but it should be close and apart from replace_all_with_lowest() fairly easy to convert to actual SLIC). Note that you actually need a double loop to cycle through all map tiles (x and y).

Code:

current_ID = 1;

loop (maptiles) {
	current_tile = <next tile>;

	if (is_land(current_tile)) {
		loop (neighbours) {
			if (is_land(neighbour)) {
				continent_ID[current_tile] = continent_ID(neighbour);
			}
			if (multiple_land_IDs_found) {
				replace_all_with_lowest();
			}
		}
		if (continent_ID[current_tile] = 0) {
			current_ID++;
			continent_ID[current_tile] = current_ID;
		}
	} else {
		loop (neighbours) {
			if (!is_land(neighbour)) {
				continent_ID[current_tile] = continent_ID(neighbour);
			}
			if (multiple_land_IDs_found) {
				replace_all_with_lowest();
			}
		}
		if (continent_ID[current_tile] = 0) {
			current_ID++;
			continent_ID[current_tile] = -1*current_ID;
		}
	}
}

**Immortal Wombat** · May 28, 2003, 15:20

Well GoodMod does a fair number of calls to CreateLocation, it scans the map four times is it? And this is 8. It would be amazingly useful though.

The only thing I can see that won't work so directly as that would be using the current_tile as an array element, it being a pair of coordinates. I've been using 100*x + y to get two numbers in when using units I think it was for some reason. but the map could be all different sizes, and to do 1000*x + y seems a little large. Is there a better way to do it?

**Locutus** · May 28, 2003, 15:35

The best way to do it (and how I've always done it in the past), is x + y * g.mapheight (or x * g.mapwidth +y, whatever you prefer). Can't get it more efficient than that...

I was indeed going to look into goodmod as well: maybe this could be merged with Martin's loops to reduce redundancy. But as I said, that's only in the brainstorm phase for now, I don't have anything tangible on that yet.

**Martin Gühmann** · May 29, 2003, 11:37

Originally posted by Immortal Wombat
Well GoodMod does a fair number of calls to CreateLocation, it scans the map four times is it? And this is 8. It would be amazingly useful though.

And even the CreateLocation function is not the slowest part of the code. IIRC the slowest part is removing all these help tile improvements. Maybe I should rewrite the code and also modify the tileimprovements so that they can be placed on the terrain without the need that the terrain has to be owned.

-Martin

**Martin Gühmann** · October 18, 2003, 14:00

What about this stuff?

Code:

////////////////////////////////////////////////////////
//MG_ComputeContinents                                //
//                                                    //
//Parameter: location_t theLoc                        //
//A location                                          //
//Parameter: int_t GetID                              //
//Determinzes what the function returns.              //
//                                                    //
//Return Value:                                       //
//Returns a continent ID if GetID == 1, that is unique//
//for each coherent mass of Land or of water. If the  //
//continent is a land mass the return value is        //
//positive, if it is a water mass the return value is //
//negative.                                           //
//If GetID == 0 it returns the size of the continent  //
//of that theLoc is part of.                          //
//if GetID == 2 it returns the number of continents on//
//the whole map. Else it returns the same value as    //
//GetID == 1.                                         //
//                                                    //
//Remarks:                                            //
//MG_IsLand needs to be modified if you change the    //
//number of terrains in the terrain.txt.              //
////////////////////////////////////////////////////////

int_f MG_ComputeContinents(location_t theLoc, int_t GetID){
	int_t IsInitialized;
	int_t i;
	int_t q;
	int_t r;
	int_t MGContinentIDs[];//GetMapWidth() * GetMapHeight()
	int_t MGContinentSizes[];
	int_t MGLastID;
	location_t MGIDLoc;
	location_t MGLoc1;
	location_t MGLoc2;
	int_t MGGetID;
	MGGetID = GetID;
	MGIDLoc = theLoc;
	if(!IsInitialized){
		IsInitialized = 1;
		MGLastID = 1;
		for(i = 0; i < GetMapWidth() * GetMapHeight(); i = i + 1){
			MGContinentIDs[i] = 0;
		}
		location_t MGSameLocs[];
		location_t MGDifferentLocs[];
		int_t indexS;
		int_t indexD;
		indexS = 1;
		indexD = 1;
		MakeLocation(MGLoc1, 0, 0);
		MGDifferentLocs[0] = MGLoc1;
		q = 0;
		r = 0;
		while(q < MGDifferentLocs.#){
			MGLoc1 = MGDifferentLocs[q];
			q = q + 1;
			if(MGContinentIDs[MGLoc1.x + MGLoc1.y * GetMapWidth()] == 0){
				MGSameLocs[indexS] = MGLoc1;
				indexS = indexS + 1;
				while(MGSameLocs.# > r){
					MGLoc1 = MGSameLocs[r];
					r = r + 1;
					if(MGContinentIDs[MGLoc1.x + MGLoc1.y * GetMapWidth()] == 0){
						if(MG_IsLand(MGLoc1)){
							MGContinentIDs[MGLoc1.x + MGLoc1.y * GetMapWidth()] = MGLastID;
						}
						else{
							MGContinentIDs[MGLoc1.x + MGLoc1.y * GetMapWidth()] = -1 * MGLastID;
						}
						for(i = 0; i < 8; i = i + 1){
							if(GetNeighbor(MGLoc1, i, MGLoc2)){
								if(MGContinentIDs[MGLoc2.x + MGLoc2.y * GetMapWidth()] == 0){
								//	if(MG_IsLand(MGLoc2) == MG_IsLand(MGLoc1)){
									if(MG_IsLand(MGLoc2) == (MGContinentIDs[MGLoc1.x + MGLoc1.y * GetMapWidth()] > 0)){
										MGSameLocs[indexS] = MGLoc2;
										indexS = indexS + 1;
									}
									else{
										MGDifferentLocs[indexD] = MGLoc2;
										indexD = indexD + 1;
									}
								}
							}
						}
					}
				}
				MGLastID = MGLastID + 1;
			}
		}
		MGContinentSizes[MGLastID - 1] = 0;
		for(i = 0; i < MGContinentIDs.#; i = i + 1){
			if(MGContinentIDs[i] > 0){
				MGContinentSizes[MGContinentIDs[i]] = MGContinentSizes[MGContinentIDs[i]] + 1;
			}
			elseif(MGContinentIDs[i] < 0){
				MGContinentSizes[-MGContinentIDs[i]] = MGContinentSizes[-MGContinentIDs[i]] - 1;
			}
		}
	}
	if(GetID == 1){
		return MGContinentIDs[MGIDLoc.x + MGIDLoc.y * GetMapWidth()];
	}
	elseif(GetID == 0){
		int_t MGCon;
		MGCon = MGContinentIDs[MGIDLoc.x + MGIDLoc.y * GetMapWidth()];
		if(MGCon > 0){
			return MGContinentSizes[MGCon];
		}
		elseif(MGCon < 0){
			return MGContinentSizes[-MGCon];
		}
	}
	elseif(GetID == 2){
		return MGContinentSizes.#;
	}
	else{
		return MGContinentIDs[MGIDLoc.x + MGIDLoc.y * GetMapWidth()];
	}
}

////////////////////////////////////////////////////////
//MG_AreOnSameContinent                               //
//                                                    //
//Parameter: location_t firstLoc                      //
//A location                                          //
//Parameter: location_t secondLoc                     //
//A location                                          //
//                                                    //
//Return Value:                                       //
//Returns 1 if both locations are on the same         //
//continent, otherwise it returns 0.                  //
//                                                    //
//Remarks:                                            //
//MG_IsLand needs to be modified if you change the    //
//number of terrains in the terrain.txt.              //
////////////////////////////////////////////////////////

int_f MG_AreOnSameContinent(location_t firstLoc, location_t secondLoc){
	location_t MGFirstLoc;
	location_t MGSecondLoc;
	MGFirstLoc = firstLoc;
	MGSecondLoc = secondLoc;
	return (MG_ComputeContinents(MGFirstLoc, 1) == MG_ComputeContinents(MGSecondLoc, 1));
}

////////////////////////////////////////////////////////
//MG_GetContinentID                                   //
//                                                    //
//Parameter: location_t theLoc                        //
//                                                    //
//Return Value:                                       //
//The continent ID of theLoc's continent.             //
//                                                    //
//Remarks:                                            //
//MG_IsLand needs to be modified if you change the    //
//number of terrains in the terrain.txt.              //
////////////////////////////////////////////////////////

int_f MG_GetContinentID(location_t theLoc){
	location_t MGLoc;
	MGLoc = theLoc;
	return MG_ComputeContinents(MGLoc, 1);
}

////////////////////////////////////////////////////////
//MG_GetContinentSize                                 //
//                                                    //
//Parameter: location_t theLoc                        //
//                                                    //
//Return Value:                                       //
//The continent size of theLoc's continent.           //
//                                                    //
//Remarks:                                            //
//MG_IsLand needs to be modified if you change the    //
//number of terrains in the terrain.txt.              //
////////////////////////////////////////////////////////

int_f MG_GetContinentSize(location_t theLoc){
	location_t MGLoc;
	MGLoc = theLoc;
	return MG_ComputeContinents(MGLoc, 0);
}

////////////////////////////////////////////////////////
//MG_GetNumberOfContinents                            //
//                                                    //
//Parameter: none                                     //
//                                                    //
//Return Value:                                       //
//The number of continents on the map.                //
//                                                    //
//Remarks:                                            //
//MG_IsLand needs to be modified if you change the    //
//number of terrains in the terrain.txt.              //
////////////////////////////////////////////////////////

int_f MG_GetNumberOfContinents(){
	location_t MGLoc;
	MakeLocation(MGLoc, 0, 0);
	return MG_ComputeContinents(MGLoc, 2);
}

-Martin

**The Big Mc** · October 18, 2003, 16:14

looks like some poor poor person got some work to do

**Martin the Dane** · October 19, 2003, 04:24

Martin,

I just scanned through your code and noticed that you used GetMapWidth() and GetMapHeight() several times within a loop.

Depending on the implementation of these functions this might be OK, but as we do not know how this is implemented (yet), you could most likey speed up the process considerabely by reading these values once and placing them in variables.

The same goes for the "for(i = 0; i < GetMapWidth() * GetMapHeight(); i = i + 1)" here "GetMapWidth() * GetMapHeight()" is (most likely) calculated once for every map-square.

Some (probably most) modern compilers takes this into account but I doubth that the slic-script engine does that.

When I learned to program (back in the days where I was one of a select few that had a 486DX with 4 MB of RAM - 386DX with 1MB was considered a fast computer) I learnd a very usefull rule: "Never put any line of code within a loop that can in any way be placed outside it" in other words "put as little code as possible into loops."

**Martin Gühmann** · October 19, 2003, 10:40

Originally posted by The Big Mc
looks like some poor poor person got some work to do

That is not much I just posted less then 200 lines of a script that contains nearly 3000 lines, well including comments.

And this script just contains a lot of function.

Well Martin I replaced the GetMapWidth and GetMapHeight functions by integers. But the function still needs one or two seconds on a 70*140 map to calculate all the stuff. That is not faster than the original function. And actual I don't care to much about it, because the function is selfreinitializing.

That means if all the stuff is calculated the whole data is stored in the MGContinentIDs array until the next /reloadslic and IsInitialized is 1 until the next /reloadslic as well.

Well I would rather worry about memory usage and redundancy. I know for example that MGDifferentLocs[] can be filled with a lot of location.

-Martin

Announcement

City on same continent

City on same continent

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment