Advertisement
Civilization Fanatics' Center  

Go Back   Civilization Fanatics' Forums > CIVILIZATION IV > Civ4 - Creation & Customization > Civ4 - SDK/Python

Reply
 
Thread Tools
Old Aug 24, 2008, 01:09 AM   #1
Maniac
Apolyton Sage
 
Maniac's Avatar
 
Join Date: Nov 2004
Location: Gent, Belgium
Posts: 5,576
[SDK] How to make the pathfinder understand "cliff" terrain?

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:

Code:
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?
__________________
Contraria sunt Complementa. -- Niels Bohr
Completed Mods: SMAniaC (SMAC) | Planetfall (Civ4)

Last edited by Maniac; Aug 24, 2008 at 04:27 AM.
Maniac is offline   Reply With Quote
Old Aug 24, 2008, 04:07 AM   #2
EmperorFool
Deity
 
EmperorFool's Avatar
 
Join Date: Mar 2007
Location: Mountain View, California
Posts: 9,625
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.
__________________
Monkeys killing monkeys killing monkeys over pieces of the ground.
Silly monkeys, give them thumbs they make a club and beat their brother down.


BUG Mod - BTS Unaltered Gameplay
[ Forum | Download | FAQ | Known Issues | Troubleshooting | Modding Tutorial ]

BAT 3.0.1 QuickFix™ released Oct 24th
EmperorFool is offline   Reply With Quote
Old Aug 24, 2008, 06:47 AM   #3
Maniac
Apolyton Sage
 
Maniac's Avatar
 
Join Date: Nov 2004
Location: Gent, Belgium
Posts: 5,576
Quote:
Originally Posted by EmperorFool View Post
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)

Code:
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;
					}
				}
			}
		}
	}
Quote:
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
__________________
Contraria sunt Complementa. -- Niels Bohr
Completed Mods: SMAniaC (SMAC) | Planetfall (Civ4)

Last edited by Maniac; Aug 24, 2008 at 06:59 AM.
Maniac is offline   Reply With Quote
Old Aug 24, 2008, 01:36 PM   #4
EmperorFool
Deity
 
EmperorFool's Avatar
 
Join Date: Mar 2007
Location: Mountain View, California
Posts: 9,625
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.
__________________
Monkeys killing monkeys killing monkeys over pieces of the ground.
Silly monkeys, give them thumbs they make a club and beat their brother down.


BUG Mod - BTS Unaltered Gameplay
[ Forum | Download | FAQ | Known Issues | Troubleshooting | Modding Tutorial ]

BAT 3.0.1 QuickFix™ released Oct 24th
EmperorFool is offline   Reply With Quote
Old Aug 30, 2008, 03:59 PM   #5
Maniac
Apolyton Sage
 
Maniac's Avatar
 
Join Date: Nov 2004
Location: Gent, Belgium
Posts: 5,576
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.

Code:
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;
}
__________________
Contraria sunt Complementa. -- Niels Bohr
Completed Mods: SMAniaC (SMAC) | Planetfall (Civ4)
Maniac is offline   Reply With Quote
Old Sep 01, 2008, 04:07 PM   #6
EmperorFool
Deity
 
EmperorFool's Avatar
 
Join Date: Mar 2007
Location: Mountain View, California
Posts: 9,625
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?
__________________
Monkeys killing monkeys killing monkeys over pieces of the ground.
Silly monkeys, give them thumbs they make a club and beat their brother down.


BUG Mod - BTS Unaltered Gameplay
[ Forum | Download | FAQ | Known Issues | Troubleshooting | Modding Tutorial ]

BAT 3.0.1 QuickFix™ released Oct 24th
EmperorFool is offline   Reply With Quote
Old Sep 02, 2008, 06:27 PM   #7
Maniac
Apolyton Sage
 
Maniac's Avatar
 
Join Date: Nov 2004
Location: Gent, Belgium
Posts: 5,576
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.
__________________
Contraria sunt Complementa. -- Niels Bohr
Completed Mods: SMAniaC (SMAC) | Planetfall (Civ4)
Maniac is offline   Reply With Quote
Old Sep 02, 2008, 08:22 PM   #8
EmperorFool
Deity
 
EmperorFool's Avatar
 
Join Date: Mar 2007
Location: Mountain View, California
Posts: 9,625
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:

Code:
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:

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.
__________________
Monkeys killing monkeys killing monkeys over pieces of the ground.
Silly monkeys, give them thumbs they make a club and beat their brother down.


BUG Mod - BTS Unaltered Gameplay
[ Forum | Download | FAQ | Known Issues | Troubleshooting | Modding Tutorial ]

BAT 3.0.1 QuickFix™ released Oct 24th
EmperorFool is offline   Reply With Quote
Old Sep 03, 2008, 06:09 PM   #9
Maniac
Apolyton Sage
 
Maniac's Avatar
 
Join Date: Nov 2004
Location: Gent, Belgium
Posts: 5,576
Update report:

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

Adding this
Spoiler:
Code:
	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.
__________________
Contraria sunt Complementa. -- Niels Bohr
Completed Mods: SMAniaC (SMAC) | Planetfall (Civ4)

Last edited by Maniac; Sep 03, 2008 at 07:03 PM.
Maniac is offline   Reply With Quote
Old Sep 03, 2008, 08:29 PM   #10
Maniac
Apolyton Sage
 
Maniac's Avatar
 
Join Date: Nov 2004
Location: Gent, Belgium
Posts: 5,576
Eureka!

I modified this code in pathvalid
Code:
	if (pSelectionGroup->atPlot(pFromPlot))
	{
		return TRUE;
	}
to

Code:
	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.
__________________
Contraria sunt Complementa. -- Niels Bohr
Completed Mods: SMAniaC (SMAC) | Planetfall (Civ4)

Last edited by Maniac; Sep 03, 2008 at 08:39 PM.
Maniac is offline   Reply With Quote
Old Sep 03, 2008, 08:49 PM   #11
EmperorFool
Deity
 
EmperorFool's Avatar
 
Join Date: Mar 2007
Location: Mountain View, California
Posts: 9,625
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.
__________________
Monkeys killing monkeys killing monkeys over pieces of the ground.
Silly monkeys, give them thumbs they make a club and beat their brother down.


BUG Mod - BTS Unaltered Gameplay
[ Forum | Download | FAQ | Known Issues | Troubleshooting | Modding Tutorial ]

BAT 3.0.1 QuickFix™ released Oct 24th
EmperorFool is offline   Reply With Quote
Old Sep 03, 2008, 08:52 PM   #12
Maniac
Apolyton Sage
 
Maniac's Avatar
 
Join Date: Nov 2004
Location: Gent, Belgium
Posts: 5,576
sorry I mistyped. I edited the pathvalid function.
__________________
Contraria sunt Complementa. -- Niels Bohr
Completed Mods: SMAniaC (SMAC) | Planetfall (Civ4)
Maniac is offline   Reply With Quote
Reply

Bookmarks

Go Back Civilization Fanatics' Forums > CIVILIZATION IV > Civ4 - Creation & Customization > Civ4 - SDK/Python > [SDK] How to make the pathfinder understand "cliff" terrain?

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
"Black Terrain" FIX for NVIDIA! FIX for "Insert Correct CD"! x0manowar Civ4 - Technical Support 1 Dec 11, 2011 01:38 PM
Whats is considered a "Team" in the SDK.. as compared to a "Player" Kailric Civ4 - SDK/Python 1 May 14, 2008 03:02 AM
Young people have messed up priorities or the "Puppy thrown off a cliff" thread mrt144 Off-Topic 64 Mar 09, 2008 12:24 PM
Don't understand AI's "place city" logic. What am I missing? jpinard Civ4 - General Discussions 49 Aug 13, 2007 05:50 PM
how to make new terrain "Mountain" wicked_1 Civ4 - Creation & Customization 2 Feb 07, 2006 01:08 PM


Advertisement

All times are GMT -6. The time now is 07:26 AM.


Powered by vBulletin®
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
This site is copyright © Civilization Fanatics' Center.
Support CFC: Amazon.com | Amazon UK | Amazon DE | Amazon CA | Amazon FR