[PYTHON/MOD-COMP] A* Pathfinder + Move Highlighter

12monkeys

Prince
Joined
Nov 24, 2003
Messages
440
Location
Germany, Europe
--------------------------------------------------
Name : AStar Pathfinder + Move Highlighter
Version : v1.1
Date : 12.03.06
Author : 12monkeys (@civfanatics + @apolyton)
--------------------------------------------------

Motivation :
-------------
- The initial idea was born in a thread in the C&C forum, when The Great Apple posted a small feature which highlights the move area of an unit. After some tries and discussions this great idea stucks due to the lack of a usable function to calculate the movement costs for a unit between plot A and B. Because thebuilt-in path finding function is not usable from python, I didn't though that we could solve this problem. Then belizan stated, that a path finding algorithm is quite a usual problem in that it could be as fast as the in built one. That gave me the push! After some investigation I found the A* path finding algorithm and started to create this small component.


Features :
-------------
AStarTools.py provides two classes for external use:
- AStar() :
contains some functions to calculate the shortest path between two plots for a specific unit. Although the calculated path is different from the one the built-in pathfinder creates, the calculated movement costs are the same (at least during my tests). The built-in pathfinder, creates more smooth pathes, while my one creates more zig-zag pathes. It also provides you with functions to calculate the area a unit can move to within its remaining movement points.
- AStarMoveArea() :
contains a function to highlight/dehighlight the area a unit can move to. The area will be calculated by class AStar(). It is highlighted with colored brackets, where the color codes some information about the plot itself. The function takes consideration of not revealed plots and visible or invisible units (as subs and spies).

For details about the usage of the two classes, have a look in the code example attached and into the AStarTools.py file itself. In the header of each class as well as in the definition of the main methods is some more information.

CvHighlightEvents.py is a sample implementation for the AStar classes as well as a small modcomp. As soon as you click on an already selected unit, all plots the unit can move to are highlighted. Ther single plots are color coded and have the following meaning :
- white : neither units not foreign territory on that plot
- cyan : indicate barbarians, where darkcyan is barbarian toeeritory (huts) and cyan are barbarian units.
- red : indicates enemies, where darkred is enemy territory and red are enemy units.
- yellow : indicate neutrals, where darkyellow is neutral territory and yellow are neutral units.


Files :
-------------
\MonkeysTools\AStarTools.py :
- contains the above mentioned classes. In former versions the folder was named "MyTools".
\CvHighlightEvents.py :
- the movement highlighter. Contains the acall of the AStar methods. Idea and implementation copied from The Great Apples code.
\entrypoints\CvEventInterface.py :
- has to be modified to hook up CvHighlightEvents.py (again, copied from The Great Apple)
\INIParser\* :
- code by Dr. Elmer Jiggle to retrieve data from INI file. Attention : found a small bug in there which I corrected. Now it is are able to retrieve data from INI files in your "My Documents" folder, when you changed the default installation directory to something else than "Sid Meier's Civilization 4" (as I did :( ).


Requirements :
-------------
- Civ4 patch 1.52 or 1.61


Installation :
-------------
- copy the files from the ZIP into their corresponding folders in the "My Documents\My Games\Civilization 4" folder. Installation at own risk!. If you have already a modified versions of any file in this mod, you can manually merged them by looking for the comments "12monkeys - <mod name> - begin/end"
Copy the AStarTools.INI into the folder "My Documents\My Games\Sid Meier's Civilization 4" (or how ever its is named on your computer ;) )


Issues :
-------------
- when there is a foreign submarine in sight of a unit which usually is not able to detect subs, it will be detected (colored frame) as soon as there is an own destroyer nearby, although the sub is not in sight of the destroyer. Currently no idea how to fix that.
- the paths created by my A* algorithm need to be more smoother, although the results is cost optimized.


Ideas for future realeases :
-------------
- needs to be expanded to handle unit stacks


Release Notes :
-------------
v1.1 :
- added color configuration by INI file (thx TheLopez for this idea)
- fixed a bug which causes a crash under special circumstances (thx Belizan for reporting it)

v1.0 :
- initial release


Credits :
-------------
- The Great Apple
for the inital idea and motivation
- Belizan
for giving me a "push"
- Patrick Lester
for his webpage describing the A* algorithm
- nameless other people
for creation of the A* algorithm
 

Attachments

  • CustomAssets_MoveHighlighter-v1.0.zip
    10.2 KB · Views: 327
  • Civ4ScreenShot0012.JPG
    Civ4ScreenShot0012.JPG
    121.5 KB · Views: 1,720
  • Civ4ScreenShot0013.JPG
    Civ4ScreenShot0013.JPG
    104.1 KB · Views: 1,367
  • Civ4ScreenShot0014.JPG
    Civ4ScreenShot0014.JPG
    129.2 KB · Views: 1,305
  • CustomAssets_MoveHighlighter-v1.1.zip
    15.3 KB · Views: 456
12Monkeys this is very cool. :goodjob:
 
TGA, I didn't think you had access to Civ4.
 
TheLopez said:
TGA, I didn't think you had access to Civ4.
I don't. By "getting home" I mean returning from uni, which I should be doing next week.

About the mod: Why do you have blue for barbarian units? Why not treat them the same as enemy units?
 
I just wanted to mark them as a seperate type of opponent, that's all. In any case, all those colors can be changed very easily in the constructor of the AStarMoveArea() class. If you don't like a color, replace it with any other color from the Civ4ColorVals.xml file.
 
12monkeys said:
I just wanted to mark them as a seperate type of opponent, that's all. In any case, all those colors can be changed very easily in the constructor of the AStarMoveArea() class. If you don't like a color, replace it with any other color from the Civ4ColorVals.xml file.

Maybe you should expose all of the things that can have their colors changed through an INI file so people don't have to "monkey" around with the python code?

Just an idea :)
 
You seem to have a bug, at least when I use it. I didn't track down the cause, just made a little work around. Sometimes the color in highlightMoves() is None, which causes an exception (and given it's called from update, that's.. bad).

Code:
			if color != "COLOR_CLEAR":
				message = "Coloring Plot %d, %d to %s" %(plot[0], plot[1], color)
				#CyInterface().addMessage(0,True,len(message),message,'',0,'Art/Interface/Buttons/Units/Fighter.dds',ColorTypes(7),0,0,True,True)
				if(color != None):
				    CyEngine().addColoredPlotAlt(plot[0], plot[1], PlotStyles.PLOT_STYLE_TARGET, self.PLE_HIGHLIGHT_PLOTS, color, .5)

Solved the problem for me, and the code behaves fine (So the None colors were intended to be skipped). I noticed it never occurs with the first unit, but with subsequent units after one has been moved.
 
TheLopez said:
Maybe you should expose all of the things that can have their colors changed through an INI file so people don't have to "monkey" around with the python code?

Just an idea :)

Done! thx for that idea!

BTW : I digged out a bug in Dr. Elmar Jiggles INI Parser. If you changed the Civ 4 installation directory name from "Sid Meier's Civilization 4" to something else (I used just "Civilization 4") than the function _getUserDir() in CvPath.py failed to create the correct path. That makes it impossible to use INI files in your the user directory. I fixed that.
 
Belizan said:
You seem to have a bug, at least when I use it. I didn't track down the cause, just made a little work around. Sometimes the color in highlightMoves() is None, which causes an exception (and given it's called from update, that's.. bad).

Code:
			if color != "COLOR_CLEAR":
				message = "Coloring Plot %d, %d to %s" %(plot[0], plot[1], color)
				#CyInterface().addMessage(0,True,len(message),message,'',0,'Art/Interface/Buttons/Units/Fighter.dds',ColorTypes(7),0,0,True,True)
				if(color != None):
				    CyEngine().addColoredPlotAlt(plot[0], plot[1], PlotStyles.PLOT_STYLE_TARGET, self.PLE_HIGHLIGHT_PLOTS, color, .5)

Solved the problem for me, and the code behaves fine (So the None colors were intended to be skipped). I noticed it never occurs with the first unit, but with subsequent units after one has been moved.


I think I found the reason. Under some circumstances, the color values of some plots are not set. I changed that. Should be fixed now.

Thx for reporting this bug.
 
Issues :
-------------
- when there is a foreign submarine in sight of a unit which usually is not able to detect subs, it will be detected (colored frame) as soon as there is an own destroyer nearby, although the sub is not in sight of the destroyer. Currently no idea how to fix that.
Wie wäre es mit einer Abfrage, ob die Einheit, die zu sehen ist, unsichtbar ist, wenn dies der Fall ist, gebe dem Feld die Farbe grau, oder so ähnlich.
 
Caesium said:
Wie wäre es mit einer Abfrage, ob die Einheit, die zu sehen ist, unsichtbar ist, wenn dies der Fall ist, gebe dem Feld die Farbe grau, oder so ähnlich.

Thats exactly what is done. The problem is more difficult. Invisible units are not displayed. They are only displayed if you select a unit which is able to detect the sub. But I can't check if a unit is in sight of a specific unit, I can only check if a unit is in sight of ANY unit. That results in the following problem :
Lets assume:
- a sub is at plot (1;1)
- a batlehorsehockyp is at plot (1;2).
- a destroyer is at plot (1;5).

That means :
- the sub would be able to see the sub, in case it would not be invisible or it would attack the battleship.
- the sub is in the moving range, but not in the sight range of the destroyer.

When you now select the destroyer, the plot of the sub would be marked as enemy plot although it could not be seen by any unit.

Why? The program logic checks :

(is the sub is in visible range of any unit -> yes (battleship))
AND
(is the sub in the moving range of the selected unit -> yes (destroyer))
AND
(
(is the sub not invisible -> no)
OR
(is the selected unit able to detect the sub -> yes)
)
-> result : mark the plot as enemy plot.

So the main problem is, I can't check if the sub is in visible range of the selected unit, I can only check if the sub is in visible range of ANY unit.
 
Oh I see.
Maybe with the patch there will be a possibility to apply this.
 
So, err. In the PLE post it says if you want to enable displaying of movement squares when the unit is clicked then you should check this thread. Does it really mean download and install this mod?
 
Porges said:
So, err. In the PLE post it says if you want to enable displaying of movement squares when the unit is clicked then you should check this thread. Does it really mean download and install this mod?

Yes, its this mod here you need. You don't need to install the AStarTools.py, and the \INIParser\*.py files because its already in the PLE mod.
 
Question: Instead of the plot highlights which are little lines in the corners of each plot, can the highlighted area be made to 'glow' similar to an 'owned' plot near a city? If this is possible I would make the 'glow' dimmer than the 'owned area' glow.

I think the current highlights are too distracting and a slight glow would look better.
 
I just discovered this mod and really like the idea, unfortunately I found a rather major bug (how is it that no one ever noticed it before?), movement for units starting on a Hill/forest is wrong. I suspect the movement cost of the starting tile is being subtracted for the unit which is incorrect as Civ4 only counts the cost of the tile moved into. I've beat my head against the problem for several hours and couldn't make any headway as I cant get any kind of feedback on what totals its coming up with as it runs. I suspect it someware in these lines (146, 152)

Code:
# calculate movement cost from root plot to new plot
if self.pCloseList.exists(pPlot):
	iParentGCosts = self.pCloseList.getGCosts(pPlot)
else:
	iParentGCosts = self.pOpenList.getGCosts(pPlot)
iGCosts = pPlot.movementCost(self.pUnit, pNewPlot) + iParentGCosts
if (self.bIgnoreMovesLeft) or (iGCosts <= self.iMovesLeft):

Here are some screen shots demonstrating the bug, just move any 2 move unit onto hill or forest to replicate. I've also updated the mod to use the more advanced Giggles Event manager rather then its own making it easy to add to existing mods, just put the folder in Python directory and add

import MoveHighlighter at the top and then register it with

MoveHighlighter.MoveHighlighter(self) in the registration area

The INIParser is also required, but everyone has that so I didn't include it.
 

Attachments

  • Civ4ScreenShot0016.JPG
    Civ4ScreenShot0016.JPG
    149.3 KB · Views: 229
  • MoveHighlighter.zip
    8.9 KB · Views: 242
I just discovered this mod and really like the idea, unfortunately I found a comment describing a rather weird bug ... I though, I'd better clear that before I install & remove again ...
movement for units starting on a Hill/forest is wrong. I suspect the movement cost of the starting tile is being subtracted for the unit which is incorrect as Civ4 only counts the cost of the tile moved into. I've beat my head against the problem for several hours and couldn't make any headway as I cant get any kind of feedback on what totals its coming up with as it runs. I suspect it someware in these lines (146, 152)
Code:
if self.pCloseList.exists(pPlot):
	iParentGCosts = self.pCloseList.getGCosts(pPlot)
else:
	iParentGCosts = self.pOpenList.getGCosts(pPlot)
iGCosts = pPlot.movementCost(self.pUnit, pNewPlot) + iParentGCosts #########
So I had a look on the code ... found something ...

Entry 164 for CyPlot in the API Reference says:
INT movementCost (CyUnit pUnit, CyPlot pFromPlot)
int (CyUnit* pUnit, CyPlot* pFromPlot)

pFromPlot!! Rather counterintuitive at first sight, but then becoming more familiar ... Doesn't this simply mean that target and origin plots are just mistakenly switched in the MOD??! There it is used in old -> new direction. (the surrounding code)
So the line above should read:
Code:
iGCosts = pNewPlot.movementCost(self.pUnit, pPlot) + iParentGCosts
then I searched the forums ... finally found this code being part of BUG/BAT now, GREAT I thought, but am uncertain now. This part of code is untouched.
Have now the same question as Impaler[WrG]: (how is it that no one ever noticed it before?)
Is this bug still active? Or am I simply wrong?:crazyeye:

EDIT
[the whole difference is that the way from B to A is calculated, instead of the way from A to B, which as we all know is not always the same in CIV ...
Could somebody with a current BUG/BAT installation confirm please?]
 
[...]

So I had a look on the code ... found something ...

Entry 164 for CyPlot in the API Reference says:
INT movementCost (CyUnit pUnit, CyPlot pFromPlot)
int (CyUnit* pUnit, CyPlot* pFromPlot)

pFromPlot!! Rather counterintuitive at first sight, but then becoming more familiar ... Doesn't this simply mean that target and origin plots are just mistakenly switched in the MOD??! There it is used in old -> new direction. (the surrounding code)
So the line above should read:
Code:
iGCosts = pNewPlot.movementCost(self.pUnit, pPlot) + iParentGCosts
then I searched the forums ... finally found this code being part of BUG/BAT now, GREAT I thought, but am uncertain now. This part of code is untouched.
Have now the same question as Impaler[WrG]: (how is it that no one ever noticed it before?)
Is this bug still active? Or am I simply wrong?:crazyeye:

EDIT
[the whole difference is that the way from B to A is calculated, instead of the way from A to B, which as we all know is not always the same in CIV ...
Could somebody with a current BUG/BAT installation confirm please?]

Interesting...
I'm using 12monkeys' A* Pathfinder in my "Imperial Roads" module and I never noticed that bug. Well, in my case it makes no different because I'm adding the 'starting' plot manualy to the list and it's only for calculating the costs and the time for the road prodject. But I was going to use this A* tool for another module of mine and thx to you this could prevent some awkward outcomes. :goodjob:
 
Top Bottom