1. We have added the ability to collapse/expand forum categories and widgets on forum home.
    Dismiss Notice
  2. All Civ avatars are brought back and available for selection in the Avatar Gallery! There are 945 avatars total.
    Dismiss Notice
  3. To make the site more secure, we have installed SSL certificates and enabled HTTPS for both the main site and forums.
    Dismiss Notice
  4. Civ6 is released! Order now! (Amazon US | Amazon UK | Amazon CA | Amazon DE | Amazon FR)
    Dismiss Notice
  5. Dismiss Notice
  6. Forum account upgrades are available for ad-free browsing.
    Dismiss Notice

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

Discussion in 'Civ4 - SDK/Python' started by Maniac, Aug 24, 2008.

  1. Maniac

    Maniac Apolyton Sage

    Joined:
    Nov 27, 2004
    Messages:
    5,582
    Location:
    Gent, Belgium
    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?
     
  2. EmperorFool

    EmperorFool Chieftain

    Joined:
    Mar 2, 2007
    Messages:
    9,633
    Location:
    Mountain View, California
    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.
     
  3. Maniac

    Maniac Apolyton Sage

    Joined:
    Nov 27, 2004
    Messages:
    5,582
    Location:
    Gent, Belgium
    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;
    					}
    				}
    			}
    		}
    	}
    That would be great! :goodjob:
    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...: :crazyeye:

    In CvSelectionGroup.cpp:

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

    EmperorFool Chieftain

    Joined:
    Mar 2, 2007
    Messages:
    9,633
    Location:
    Mountain View, California
    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.
     
  5. Maniac

    Maniac Apolyton Sage

    Joined:
    Nov 27, 2004
    Messages:
    5,582
    Location:
    Gent, Belgium
    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. :hmm:

    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;
    }
     
  6. EmperorFool

    EmperorFool Chieftain

    Joined:
    Mar 2, 2007
    Messages:
    9,633
    Location:
    Mountain View, California
    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?
     
  7. Maniac

    Maniac Apolyton Sage

    Joined:
    Nov 27, 2004
    Messages:
    5,582
    Location:
    Gent, Belgium
    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. :D
     
  8. EmperorFool

    EmperorFool Chieftain

    Joined:
    Mar 2, 2007
    Messages:
    9,633
    Location:
    Mountain View, California
    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;
    	}
    
    	[B]pParentPlot = GC.getMapINLINE().plotSorenINLINE(parent->m_iX, parent->m_iY);[/B]
    
    	if ([B]pParentPlot[/B]->area() != pNewPlot->area())
    	{
    		return FALSE;
    	}
    
    [B]	if ((pParentPlot->isFlatlands() && pNewPlot->isPeak()) || (pNewPlot->isFlatlands() && pParentPlot->isPeak()))
    	{
    		return FALSE;
    	}[/B]
    
    	return TRUE;
    }
    
    You should be able to ditch all the other changes you've made with regards to path-finding, canMoveInto() and its friends.
     
  9. Maniac

    Maniac Apolyton Sage

    Joined:
    Nov 27, 2004
    Messages:
    5,582
    Location:
    Gent, Belgium
    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.
     
  10. Maniac

    Maniac Apolyton Sage

    Joined:
    Nov 27, 2004
    Messages:
    5,582
    Location:
    Gent, Belgium
    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.
     
  11. EmperorFool

    EmperorFool Chieftain

    Joined:
    Mar 2, 2007
    Messages:
    9,633
    Location:
    Mountain View, California
    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.
     
  12. Maniac

    Maniac Apolyton Sage

    Joined:
    Nov 27, 2004
    Messages:
    5,582
    Location:
    Gent, Belgium
    sorry I mistyped. I edited the pathvalid function.
     

Share This Page