[SDK] How to make the pathfinder understand "cliff" terrain?

[Maniac]

I'd like to try to add cliffs to Civ4 for Planetfall.
One way to create cliffs is recycling the Peak plottype, make them passable, workable etc.
The movement rules would be: you can't move from a cliff straight into flatland or water plots, and you can't move straight from water or flatlands into cliffs. But you can cross into a cliff from a hills plot, and vice versa.

The idea is to create easily defendable highland plateaus, bordered all round by cliffs, with only a handful 'ramps'/hills. Using unmodded completely impassable/unworkable Peaks as borders has as consequence the plateaus become too small, thus leaving too little actually worth defending...

As a test I tried this simple way of coding it into the DLL:

bool CvUnit::canMoveInto(const CvPlot* pPlot, bool bAttack, bool bDeclareWar, bool bIgnoreLoad) const
{
...

	if (plot()->isPeak())
	{
		if ((pPlot->isWater()) || (pPlot->isFlatlands()))
		{
			return false;
		}
	}

	if ((plot()->isWater()) || (plot()->isFlatlands()))
	{
		if (pPlot->isPeak())
		{
			return false;
		}
	}

It works just fine. You can't eg move from a flatlands to a peak in an adjacent plot.
However there's a big problem.
You are neither able to move directly from a flatland to a peak/cliff two tiles away, even if there's a hill in between. You need to first move to the hills, and only then you can proceed to the peak. This is very annoying for the human players, but no doubt disastrous for the AI: they would only be able to move from flatland to cliffs by pure luck.

So therefore I'm wondering, does anyone have any idea if and how it's possible to modify the pathfinder, so that it can plot paths between flatland/water and cliffs, using hills?

[EmperorFool]

To solve the immediate problem of the user having to make two discrete moves, only apply your check when the two plots are adjacent.

As for the pathfinder algorithm, does it use canMoveInto() to find routes? Or is canMoveInto() the actual path-finding code? I haven't spent much time reading the DLL code, but if you point me to the algorithm, I can take a look.

[Maniac]

Originally Posted by EmperorFool

To solve the immediate problem of the user having to make two discrete moves, only apply your check when the two plots are adjacent.

Heh, cool idea. I tried it, but it isn't really a workable solution. If you're eg on a flatlands, you can set as destination a peak two tiles away, and if there happens to be a hill on the path you took, the unit will arrive as intended. But:
1) if you want to move to an adjacent peak, the game will still not recognize you can go there by eg an adjacent hill.
2) you can set a peak more than a tile away as your destination, even if there are no surrounding hills. As a consequence the unit will start walking its way, but when it arrives on the plot adjacent to the peak, it can't proceed - its path is cancelled.

Here's the code. I'm not sure this the most efficient way of doing this:
(besides adding an "else if" I just noticed)

bool CvUnit::canMoveInto(const CvPlot* pPlot, bool bAttack, bool bDeclareWar, bool bIgnoreLoad) const
{
	int iI;
	CvPlot* pAdjacentPlot;

	for (iI = 0; iI < NUM_DIRECTION_TYPES; ++iI)
	{
		pAdjacentPlot = plotDirection(pPlot->getX_INLINE(), pPlot->getY_INLINE(), ((DirectionTypes)iI));

		if (pAdjacentPlot != NULL)
		{
			if (atPlot(pAdjacentPlot))
			{
				if (plot()->isPeak())
				{
					if ((pPlot->isWater()) || (pPlot->isFlatlands()))
					{
						return false;
					}
				}
				if ((plot()->isWater()) || (plot()->isFlatlands()))
				{
					if (pPlot->isPeak())
					{
						return false;
					}
				}
			}
		}
	}

As for the pathfinder algorithm, does it use canMoveInto() to find routes? Or is canMoveInto() the actual path-finding code? I haven't spent much time reading the DLL code, but if you point me to the algorithm, I can take a look.

That would be great!
There's no single algorithm I'm afraid as far as I can tell. There are a bunch of functions which seem related to pathfinding, but I don't understand the big picture or don't understand a lot of the code. canMoveInto() - and CanMoveOrAttackInto() and canMoveThrough(), two varieties of the canMoveInto() function - is used in a couple of the pathxxx functions.

Here are some (I presume) related functions:

In CvGameCoreUtils.py:

pathDestValid
pathHeuristic
pathCost
pathValid
pathAdd
stepDestValid
stepHeuristic
stepCost
stepValid
stepAdd

These above functions are referenced to in some getPathFinder-related function in CvMap.cpp. And getPathFinder seems used...:

In CvSelectionGroup.cpp:

FAStarNode* CvSelectionGroup::getPathLastNode() const
CvPlot* CvSelectionGroup::getPathFirstPlot() const
CvPlot* CvSelectionGroup::getPathEndTurnPlot() const
CvSelectionGroup::generatePath

[EmperorFool]

Civ4 uses the A* graph searching algorithm to find routes on the map.

At one point in the algorithm it iterates over all neighbors (adjacent plots) of plot X. At this point you need to interject a variation of your code to make peaks neighbors of only hill plots (not flatland or water).

I'm backlogged on BUG right now, so take a look at that Wikipedia entry (it's very short and has a psuedo-code implementation of the algorithm), and see if you can solve this yourself. If you need more help, post. And if you can't figure it out and I have more time, I'll delve into it later.

[Maniac]

I don't really see a similarity between the wikipedia and Firaxian code.

But I guess perhaps the "pathValid" function might be responsible for checking out neighbours?
Problem is I don't really know what parents are. And as a consequence neither do I really understand what ToPlot and FromPlot are. Statements like "canMoveOrAttackInto(pFromPlot)" look kinda strange to me.

int pathValid(FAStarNode* parent, FAStarNode* node, int data, const void* pointer, FAStar* finder)
{
	CvSelectionGroup* pSelectionGroup;
	CvPlot* pFromPlot;
	CvPlot* pToPlot;
	bool bAIControl;

	if (parent == NULL)
	{
		return TRUE;
	}

	pFromPlot = GC.getMapINLINE().plotSorenINLINE(parent->m_iX, parent->m_iY);
	FAssert(pFromPlot != NULL);
	pToPlot = GC.getMapINLINE().plotSorenINLINE(node->m_iX, node->m_iY);
	FAssert(pToPlot != NULL);

	pSelectionGroup = ((CvSelectionGroup *)pointer);

	// XXX might want to take this out...
	if (pSelectionGroup->getDomainType() == DOMAIN_SEA)
	{
		if (pFromPlot->isWater() && pToPlot->isWater())
		{
			if (!(GC.getMapINLINE().plotINLINE(parent->m_iX, node->m_iY)->isWater()) && !(GC.getMapINLINE().plotINLINE(node->m_iX, parent->m_iY)->isWater()))
			{
				return FALSE;
			}
		}
	}

	if (pSelectionGroup->atPlot(pFromPlot))
	{
		return TRUE;
	}

	if (gDLL->getFAStarIFace()->GetInfo(finder) & MOVE_SAFE_TERRITORY)
	{
		if (!(pFromPlot->isRevealed(pSelectionGroup->getHeadTeam(), false)))
		{
			return FALSE;
		}

		if (pFromPlot->isOwned())
		{
			if (pFromPlot->getTeam() != pSelectionGroup->getHeadTeam())
			{
				return FALSE;
			}
		}
	}

	if (gDLL->getFAStarIFace()->GetInfo(finder) & MOVE_NO_ENEMY_TERRITORY)
	{
		if (pFromPlot->isOwned())
		{
			if (atWar(pFromPlot->getTeam(), pSelectionGroup->getHeadTeam()))
			{
				return FALSE;
			}
		}
	}

	bAIControl = pSelectionGroup->AI_isControlled();

	if (bAIControl)
	{
		if ((parent->m_iData2 > 1) || (parent->m_iData1 == 0))
		{
			if (!(gDLL->getFAStarIFace()->GetInfo(finder) & MOVE_IGNORE_DANGER))
			{
				if (!(pSelectionGroup->canFight()) && !(pSelectionGroup->alwaysInvisible()))
				{
					if (GET_PLAYER(pSelectionGroup->getHeadOwner()).AI_getPlotDanger(pFromPlot) > 0)
					{
						return FALSE;
					}
				}
			}
		}
	}

	if (bAIControl || pFromPlot->isRevealed(pSelectionGroup->getHeadTeam(), false))
	{
		if (gDLL->getFAStarIFace()->GetInfo(finder) & MOVE_THROUGH_ENEMY)
		{
			if (!(pSelectionGroup->canMoveOrAttackInto(pFromPlot)))
			{
				return FALSE;
			}
		}
		else
		{
			if (!(pSelectionGroup->canMoveThrough(pFromPlot)))
			{
				return FALSE;
			}
		}
	}

	return TRUE;
}

[EmperorFool]

I don't see what this function does. I understand most of the lines of code, but I don't get what it is supposed to do overall.

Also, what is plotSorenINLINE()? It looks to me that it picks two plots at random that are both adjacent to the start of the path and then sees if the unit can move from one to the other. I don't see any provision for checking all plot combinations nor even making sure the two random plots are different plots.

Surely this isn't the only function that makes up their AStar algorithm. What are the others?

[Maniac]

I don't know. The list I posted in post #3 seems related, but I don't understand the big picture either. That's why I posted this thread.

[EmperorFool]

I skimmed a little of those functions, but have you tried changing stepValid()? My guess is that paths are made up of steps between adjacent plots. Here's stepValid() in English:

Stepping from null node to any node is ok.
Stepping into impassable terrain is not ok.
Stepping from one CvArea to a different CvArea is not ok.

Try using this code:

int stepValid(FAStarNode* parent, FAStarNode* node, int data, const void* pointer, FAStar* finder)
{
	CvPlot* pNewPlot;

	if (parent == NULL)
	{
		return TRUE;
	}

	pNewPlot = GC.getMapINLINE().plotSorenINLINE(node->m_iX, node->m_iY);

	if (pNewPlot->isImpassable())
	{
		return FALSE;
	}

	pParentPlot = GC.getMapINLINE().plotSorenINLINE(parent->m_iX, parent->m_iY);

	if (pParentPlot->area() != pNewPlot->area())
	{
		return FALSE;
	}

	if ((pParentPlot->isFlatlands() && pNewPlot->isPeak()) || (pNewPlot->isFlatlands() && pParentPlot->isPeak()))
	{
		return FALSE;
	}

	return TRUE;
}

You should be able to ditch all the other changes you've made with regards to path-finding, canMoveInto() and its friends.

[Maniac]

Update report:

Adding that code to stepValid doesn't have any effect on units.

Adding this

Spoiler:

	if (pFromPlot->isPeak())
	{
		if ((pToPlot->isWater()) || (pToPlot->isFlatlands()))
		{
			return FALSE;
		}
	}
	if ((pFromPlot->isWater()) || (pFromPlot->isFlatlands()))
	{
		if (pToPlot->isPeak())
		{
			return FALSE;
		}
	}

to pathValid does have as a consequence units mostly* only move to far away peaks by going through hills.

If they're on a flatland and adjacent to a peak though, they can move directly to a peak. So I guess I'll have to readd that code to canMoveInto after all.
Edit: ah no, that code had as consequence a unit's path was cancelled if it moves into a flatland next to the peak it was trying to move to, even if the flatland was simply meant to be moved through.

* There is a strange case I can't explain though:

In this 3x3 grid:

XPF
WFW
XHX

whereas:
X = doesn't matter
P = Peak
F = Flatland
W = Water
H = Hills

a unit located on the hills plotted a path to the adjacent flatland, then to the non-adjacent flatland and then to the peak. I can't really explain why that worked. Might cause problems.

[Maniac]

Eureka!

I modified this code in pathvalid

	if (pSelectionGroup->atPlot(pFromPlot))
	{
		return TRUE;
	}

to

	if (pSelectionGroup->atPlot(pFromPlot))
	{
		if (pFromPlot->isPeak())
		{
			if (!(pToPlot->isWater()) && !(pToPlot->isFlatlands()))
			{
				return TRUE;
			}
		}
		else if ((pFromPlot->isWater()) || (pFromPlot->isFlatlands()))
		{
			if (!(pToPlot->isPeak()))
			{
				return TRUE;
			}
		}
		else
		{
			return TRUE;
		}
	}

and now it works perfectly!

Thanks for the help!
Btw, EmperorFool, have you ever looked at this thread? That feature would also help make highland plateaus more easily defendable, but I can't get it to work.

[EmperorFool]

Hmm, you have a different stepValid() function than I do. Are you running 3.17? Odd that they would change something like that this late in the game.

I followed your linked thread originally and came to the same conclusion -- something else we aren't seeing must be going on.

[Maniac]

sorry I mistyped. I edited the pathvalid function.