SLG There are many detailed classifications of chess games , What this blog explains is military , It's like a high-level war 2, There are many military units , Architecture , At the same time, there are many kinds of terrain , For example, tanks can't climb mountains , Infantry can't go to sea , The moving power consumption of forest is much greater than that of plain , The fastest road ..... And so on, a series of complex settings .
Here we set up , The power consumption of plain movement is 2, Architecture for 1, The road is 1, The movement power of base infantry is 5（ Regardless of oil quantity , The movement power of each round is the same 5）
The two-dimensional coordinate class of the foundation is Point
About three classes are needed
1.GridContainer class , The core of it is two dictionaries , The terrain grid and the army grid are stored respectively
2.Node class , Independent of terrain and forces , It is only used for routing calculation
3.PathNav class , Responsible for calculating the path and moving range
The following is a brief introduction of the moving range algorithm
differ A* Three estimations of the algorithm , Only one is needed here , Oil consumption oilCost, Use one gCost{get.......} To manage , existence Node In class
PathNav Class contains three containers
1.HashSet<Node> ReachableNodeSet // Used to store accessible grids
2.List<Node> UnknownList // Used to store the grid ready to detect four points around
3.Dictionary<Point, Node> MapDic
// Maps for detection , You don't have to , But in order not to increase GridContainer The complexity of , Or will it Node It's better to make the map independent
The algorithm begins , Click infantry
Get the infantry's mobility first oilTotal=5, So calculate the farthest distance that the infantry move from top right bottom left top left bottom , Because the lowest road fuel consumption is 1, So infantry move farthest 5, One of four points 10*10（ Attention may go beyond the map , Judgment of adding one more coordinate value , And it doesn't need to be TryGet） matrix
Go through this 10*10 matrix , Use the Node Save to MapDic in ,MapDic[point]=new
Node(point, Moving force consumption constant of terrain , Types of terrain ( Forest, mountain or road )),point Is the coordinates of the current position
thus , The map is finished , Then we start to calculate the range of movement based on this map
Algorithmic thinking , Spread around from the starting point , Calculate the remaining oil at each point , If there is a surplus, it will continue to spread in four directions
therefore , The following is given Node definition , Some can be ignored for a while , It's used to calculate pathfinding
public class Node { private static int OilCostMax = 999; // Maximum fuel consumption public static
Unit startUnit; // Starting point public static Point targetPos; // Target location // The terrain type of the current location public
GridType terrainType; // current Node coordinate public Point pos; // Three properties used to calculate greed public int
fCost // { get { return gCost + hCost; } } public int gCost // Of the current grid oilCost {
get { if
(GridContainer.Instance.UnitDic.ContainsKey(pos)&&pos!=startUnit.gridID)
// There is a unit here , The road is blocked { return OilCostMax; } else if (startUnit.isInfantry() &&
(terrainType == GridType.Sea || terrainType == GridType.Reef)) // People can't go to sea { return
OilCostMax; } else if (startUnit.isPlane()) // Aircraft fixed consumption 2 { return 2; } else if
(startUnit.isShip() && terrainType != GridType.Sea) // The ship can't go ashore { return
OilCostMax; } else if (startUnit.isVehicle() && (terrainType ==
GridType.Mountain || terrainType == GridType.Sea || terrainType ==
GridType.Reef)) // Cars can't go up the mountain or down the sea { return OilCostMax; } else { return oilCost;
// All others return to the default fuel consumption } } } public int oilCost; public int hCost // Distance from target point { get {
return Math.Abs(pos.X - targetPos.X) + Math.Abs(pos.Z - targetPos.Z); } }
// How much oil is left when you move here public int oilLeft; // Parent lattice public Node parent; public Node(Point
pos, int oilCost, GridType type) { this.pos = pos; this.oilCost = oilCost;
terrainType = type; } }
We can see the oil consumption from here oilCost It is divided into actual consumption and ideal consumption , The so-called ideal consumption is the default consumption of the grid , The actual consumption is the oil consumption after considering the actual situation （ Is it a roadblock ）
According to what grid you click , What are roadblocks , It can be optimized here .
Next, calculate the moving range
Initialization starting point , Set down the oil quantity , Parent node , Pay attention to the initial point oilCost by 0, Here are some details , Be careful not to go out bug
Then add the initial point to the list to explore UnknownList
Start the cycle , As long as the list to explore is not empty , Then continue to explore
Take a node from the list , Set the parent node to the previously explored node , Calculate the fuel consumption , If the remaining oil quantity is not 0, All four nodes around the node are added to the exploration list , Keep exploring （ be careful TryGet）, Finally, delete the previously explored grid from the exploration list
Pay attention to check, do not repeat the exploration
private static void AStarCheckRange(Point startPos,int oilTotal,ref
Dictionary<Point,Node> mapDic) { Node startNode = mapDic[startPos];
startNode.oilLeft = oilTotal; startNode.parent = startNode; startNode.oilCost =
0; UnknownList.Add(startNode); startNode.oilLeft = startNode.parent.oilLeft -
startNode.oilCost; // Calculate the remaining oil quantity , loop （ This sentence can be omitted , It's just easy to understand ） while (UnknownList.Count != 0) {
Node reachableNode = UnknownList[0]; Node parent = UnknownList[0].parent;
reachableNode.oilLeft = parent.oilLeft - reachableNode.gCost; if
(reachableNode.oilLeft >= 0) // If you can get there { ReachableNodeSet.Add(reachableNode);
// Put it on the list of things that can be eliminated #region Find the four surrounding points and add them to the judgment list Node upNode; if
(mapDic.TryGetValue(reachableNode.pos.Up(), out upNode)) { if
(!ReachableNodeSet.Contains(upNode)&&!UnknownList.Contains(upNode)) {
upNode.parent = reachableNode; UnknownList.Add(upNode); } } Node rightNode; if
(mapDic.TryGetValue(reachableNode.pos.Right(), out rightNode)) { if
(!ReachableNodeSet.Contains(rightNode)&&!UnknownList.Contains(rightNode)) {
rightNode.parent = reachableNode; UnknownList.Add(rightNode); } } Node
downNode; if (mapDic.TryGetValue(reachableNode.pos.Down(), out downNode)) { if
(!ReachableNodeSet.Contains(downNode)&&!UnknownList.Contains(downNode)) {
downNode.parent = reachableNode; UnknownList.Add(downNode); } } Node leftNode;
if (mapDic.TryGetValue(reachableNode.pos.Left(), out leftNode)) { if
(!ReachableNodeSet.Contains(leftNode)&&!UnknownList.Contains(leftNode)) {
leftNode.parent = reachableNode; UnknownList.Add(leftNode); } } #endregion
// In fact, you can use circulation , I'm just too lazy to break the library design } UnknownList.RemoveAt(0); } foreach (Node node in
ReachableNodeSet) { GridContainer.Instance.TerrainDic[node.pos].SetHighLight();
// Set highlight ReachablePointSet.Add(node.pos); } }
thus ,ReachableNodeSet In the storage is all the moving range of the grid , Just highlight it
Technology