October 24, 2018 at 11:15Hexagon Maps in Unity: Path Finder, Player Squads, Animations
- Transfer
Parts 1-3: mesh, colors and cell heights;
Parts 4-7: bumps, rivers and roads;
Parts 8-11: water, landforms and fortress walls;
Parts 12-15: saving and loading, textures, distances;
Parts 16-19: path finding, player squads, animations
Parts 20-23: fog of war, map exploration, procedural generation
Parts 24-27: water cycle, erosion, biomes, cylindrical map
After calculating the distances between the cells, we proceeded to finding the paths between them.
Starting with this part, hexagon map tutorials will be created in Unity 5.6.0. It should be noted that in 5.6 there is a bug that destroys arrays of textures in assemblies for several platforms. You can get around it by including Is Readable in the texture array inspector .
Planning a trip
To search the path between two cells, we first need to select these cells. It’s more than just choosing one cell and monitoring the search on the map. For example, we will first select the initial cell, and then the final one. In this case, it would be convenient for them to become highlighted. Therefore, let's add such functionality. Until we create a sophisticated or efficient way of highlighting, we just create something to help us with the development.
One simple way to select cells is to add a path to them. The easiest way to do this is with a texture containing a hexagonal outline. Here you can download such a texture. It is transparent except for the white outline of the hexagon. Having made it white, in the future we will be able to colorize it as we need.
The cell outline on a black background.
Import the texture and set its Texture Type to Sprite . Her Sprite Mode will be set to Single with default settings. Since this is an exceptionally white texture, we do not need to convert to sRGB . The alpha channel indicates transparency, so enable Alpha is Transparency . I also set the Filter Mode texture to Trilinear , because otherwise the mip transitions for the paths might become too noticeable.
Texture Import Options
The fastest way is to add a possible contour to the cells, adding each own sprite. Create a new game object, add the Image component ( Component / UI / Image ) to it and assign it our outline sprite. Then insert the Hex Cell Label prefab instance into the scene, make the sprite object a child of it, apply the changes to the prefab, and then get rid of the prefab.
Prefab Selection Child Element
Now each cell has a sprite, but it will be too large. To make the contours match the centers of the cells, change the Width and Height of the transform component of the sprite to 17.
Selection sprites partially hidden by a relief
Since the contour is superimposed on the area of the edges of the cells, it often appears under the geometry of the relief. Because of this, part of the circuit disappears. This can be avoided by slightly raising the sprites vertically, but not in the case of breaks. Instead, we can do the following: always draw sprites on top of everything else. To do this, create your own sprite shader. It will be enough for us to copy the standard Unity sprite shader and make a couple of changes to it.
The first change is that we ignore the depth buffer, making the Z-test always succeed.
The second change is that we are rendering after the rest of the transparent geometry. Enough to add 10 to the transparency queue.
Create a new material that this shader will use. We can ignore all its properties, adhering to the default values. Then make the sprite prefab use this material.
We use our own sprite material.
Now the selection contours are always visible. Even if the cell is hidden under a higher relief, its outline will still be drawn on top of everything else. It may not look beautiful, but the selected cells will always be visible, which is useful for us.
Ignore the depth buffer
We do not want all cells to be highlighted at the same time. In fact, initially they should all be unselected. We can implement this by disabling the Image component of the Highlight prefab object .
Disabled Image component
To enable cell selection, add to the
Finally, we can specify the color so that when turned on, give the backlight a hue.
unitypackage
Now that we can select the cells, we need to move on and select two cells, and then find the path between them. First we need to select the cells, then restrict the search to a path between them, and finally show this path.
We need to select two different cells, the start and end points of the search. Suppose that to select the initial search cell, hold the left Shift key while clicking the mouse. In this case, the cell is highlighted in blue. We need to save the link to this cell for further search. In addition, when choosing a new starting cell, the selection of the old one must be disabled. Therefore, add to the
Inside,
Where to look
Instead of looking for all the distances to a cell, we are now looking for a path between two specific cells. Therefore, rename it
Now,
Turning to the search, we first need to get rid of all previous selections. Therefore, we will force to
Endpoints of a potential path
At this point, our search algorithm still calculates the distances to all cells that are reachable from the starting cell. But we don’t need it anymore. We can stop as soon as we find the final distance to the final cell. That is, when the current cell is finite, we can exit the algorithm loop.
Stop at the end point
We can find the distance between the beginning and the end of the path, but do not yet know what the real path will be. To find it, you need to track how each cell is reached. But how to do that?
When adding a cell to the border, we do this because it is a neighbor of the current cell. The one exception is the starting cell. All other cells have been reached through the current cell. If we keep track of which cell each cell was reached from, we get a network of cells as a result. More precisely, a tree-like network, the root of which is the starting point. We can use it to build the path after reaching the end point.
A tree-like network that describes the paths to the center
We can save this information by adding
We
Having reached the end point, we can visualize the path by following these links back to the starting cell and select them.
The path found
It is worth considering that often there are several shortest paths. The one found depends on the processing order of the cells. Some paths may look good, others may be bad, but there is never a shorter path. We will come back to this later.
After selecting the start point, changing the end point will trigger a new search. The same thing should happen when choosing a new starting cell. To make this possible,
Using this field, we can also initiate a new search when choosing a new beginning.
In addition, we need to avoid equal starting and ending points.
unitypackage
Although our algorithm finds the shortest path, it spends a lot of time exploring points that obviously will not become part of this path. At least it’s obvious to us. The algorithm cannot look down on the map; it cannot see that a search in some directions will be meaningless. He prefers to move on the roads, despite the fact that they are heading in the opposite direction from the end point. Is it possible to make the search smarter?
At the moment, when choosing the cell to be processed next, we consider only the distance from the cell to the beginning. If we want to do smarter, then we must also consider the distance to the end point. Unfortunately, we do not know him yet. But we can create an estimate of the remaining distance. Adding this estimate to the distance to the cell gives us an understanding of the total length of the path passing through this cell. Then we can use it to prioritize cell searches.
When we use estimation or guesswork instead of exactly known data, this is called using search heuristics. This heuristic represents the best guess of the distance left. We must determine this value for each cell that we are searching for, so we add an
How do we make an assumption about the remaining distance? In the most ideal case, we will have a road leading straight to the end point. If so, then the distance is equal to the unchanged distance between the coordinates of this cell and the final cell. Let's take advantage of this in our heuristic.
Since heuristics does not depend on a previously traveled path, it is constant in the search process. Therefore, we need to calculate it only once it
From now on, we will determine the priority of the search based on the distance to the cell plus its heuristics. Let's add values to this
For this to work, change it
Search without heuristics and with heuristics
Thanks to the new search priorities, we will actually visit fewer cells as a result. However, on a uniform map, the algorithm still processes cells that are in the wrong direction. This is because, by default, the costs for each move step are 5, and the heuristic per step adds only 1. That is, the influence of the heuristic is not very strong.
If the costs of moving on all the cards are the same, then we can use the same costs when determining the heuristic. In our case, this will be the current heuristic multiplied by 5. This will significantly reduce the number of processed cells.
We use heuristics × 5
However, if there are roads on the map, then we can overestimate the remaining distance. As a result, the algorithm can make mistakes and create a path that is actually not the shortest.
Reevaluated and valid heuristics
To ensure that the shortest path is found, we need to make sure that we never overestimate the remaining distance. This approach is called valid heuristics. Since the minimum cost of moving is 1, we have no choice but to use the same costs in determining the heuristic.
Strictly speaking, it is quite normal to use even lower costs, but this will only make the heuristic weaker. The minimum possible heuristic is zero, which gives us just Dijkstra's algorithm. With a nonzero heuristic, the algorithm is called A * (pronounced "A star").
unitypackage
Although A * is a good algorithm, our implementation is not so effective, because we use a list to store the border, which needs to be sorted at each iteration. As mentioned in the previous part, we need a priority queue, but its standard implementation does not exist. Therefore, let's create it yourself.
Our turn should support the operation of setting and exclusion from the queue based on priority. It should also support changing the priority of a cell already in the queue. Ideally, we implement it, minimizing the search for sorting and allocated memory. In addition, it should remain simple.
Create a new class
We store cell priorities in the cells themselves. That is, before adding a cell to the queue, its priority must be set. But in the event of a priority change, it will probably be useful to know what the old priority was. So let's add this in
It is also useful to know how many cells are in the queue, so add a property for this
When a cell is added to the queue, let's first use its priority as an index, treating the list as a simple array.
However, this only works if the list is long enough, otherwise we will go beyond the borders. You can avoid this by adding empty items to the list until it reaches the required length. These empty elements do not reference the cell, so they can be created by adding to the list
The list with holes
But this is how we store only one cell per priority, and most likely there will be several. To track all cells with the same priority, we need to use another list. Although we can use a real list for each priority, we can also add to the
To create a chain, let's
List of linked lists
To get a cell from a priority queue, we need to access the linked list at the lowest non-empty index. Therefore, we will go around the list in a loop until we find it. If we do not find, then the queue is empty and we return
From the found chain, we can return any cell, because they all have the same priority. The easiest way is to return the cell from the beginning of the chain.
To keep the link to the remaining chain, use the next cell with the same priority as the new start. If at this priority level there was only one cell, then the element becomes
This approach works, but iterates through the list each time a cell is received. We cannot avoid finding the smallest nonempty index, but we are not required to start from scratch every time. Instead, we can track the minimum priority and start the search with it. Initially, the minimum is essentially equal to infinity.
When adding a cell to the queue, we change the minimum as necessary.
And when withdrawing from the queue, we use at least the list for iterations, and do not start from scratch.
This significantly reduces the amount of time it takes to bypass in the priority list loop.
When changing the priority of a cell, it must be removed from the linked list of which it is a part. To do this, we need to follow the chain until we find it.
Let's start by declaring that the head of the old priority list will be the current cell, and we will also track the next cell. We can immediately take the next cell, because we know that there is at least one cell by this index.
If the current cell is a changed cell, then this is the head cell and we can cut it off as if we had pulled it out of the queue.
If this is not the case, then we need to follow the chain until we are in the cell in front of the changed cell. It contains a link to the cell that has been modified.
At this point, we can remove the changed cell from the linked list, skipping it.
After deleting a cell, you need to add it again so that it appears in the list of its new priority.
The method
Now we can take advantage of our priority queue at
Before starting the loop, the method
Change the code so that it adds and changes the neighbor. Before the change we will remember the old priority.
In addition, we no longer need to sort the border.
Search using a priority queue
As mentioned earlier, the shortest path found depends on the processing order of the cells. Our turn creates an order different from the order of the sorted list, so we can get other ways. Since we add and remove from the head of the linked list for each priority, they are more like stacks than queues. Cells added last are processed first. A side effect of this approach is that the algorithm is zigzag prone. Therefore, the likelihood of zigzag paths also increases. Fortunately, such paths usually look better, so this side effect is in our favor.
Sorted list and queue with unitypackage priority
In this part, we will divide the movement into moves and speed up the search as much as possible.
Travel from several moves
Strategy games that use hexagon nets are almost always turn-based. Units moving on the map have a limited speed, which limits the distance traveled in one turn.
To provide support for limited movement, we add in
Different types of units in the game use different speeds. Cavalry is fast, infantry is slow, and so on. We do not yet have units, so for now we will use a constant speed. Let's take a value of 24. This is a fairly large value, not divisible by 5 (the default cost of moving). Add as an argument to
In addition to tracking the total cost of moving along the path, we now also need to know how many moves it will take to move along it. But we do not need to store this information in each cell. It can be obtained by dividing the distance traveled by speed. Since these are integers, we will use integer division. That is, the total distances of no more than 24 correspond to the course 0. This means that the whole path can be completed in the current course. If the end point is at a distance of 30, then this must be turn 1. To get to the end point, the unit will have to spend all its movement in the current turn and in part of the next turn.
Let's determine the course of the current cell and all its neighbors inside
If the neighbor’s move is greater than the current move, then we crossed the boundary of the move. If the movement necessary to reach a neighbor was 1, then everything is fine. But if moving to the next cell is more expensive, then everything becomes more complicated.
Suppose that we move along a homogeneous map, that is, to get into each cell you need 5 units of movement. Our speed is 24. After four steps, we spent 20 units from our stock of movement, and there are 4 left. In the next step, 5 units are needed again, that is, one more than the available ones. What do we need to do at this stage?
There are two approaches to this situation. The first is to allow the unit to enter the fifth cell in the current turn, even if we do not have enough movement. The second is to prohibit movement during the current move, that is, the remaining movement points cannot be used and they will be lost.
The choice of option depends on the game. In general, the first approach is more appropriate for games in which units can move only a few steps per turn, for example, for games in the Civilization series. This ensures that units can always move at least one cell per turn. If units can move many cells per turn, as in Age of Wonders or in Battle for Wesnoth, then the second option is better.
Since we use speed 24, let's choose the second approach. In order for it to start working, we need to isolate the costs of getting into the next cell before adding it to the current distance.
If as a result we cross the border of the move, then first we use all the movement points of the current move. We can do this by simply multiplying the move by speed. After that, we add the cost of moving.
As a result of this, we will complete the first move in the fourth cell with 4 unused movement points. These lost points are added to the costs of the fifth cell, so its distance becomes 29, not 25. As a result, the distances are greater than before. For example, the tenth cell had a distance of 50. But now to get into it, we need to cross the borders of two moves, losing 8 movement points, that is, the distance to it now becomes 58.
Longer than expected
Since unused movement points are added to the distances to the cells, they are taken into account when determining the shortest path. The most effective way is wasting as few points as possible. Therefore, at different speeds, we can get different paths.
When we play the game, we are not very interested in the distance values used to find the shortest path. We are interested in the number of moves required to reach the end point. Therefore, instead of distances, let's display the moves.
First, get rid of
Instead, we will add to the
We use this new method in
Then we assign the neighbor’s mark the value of his move. After that, we will be able to see how many additional moves it will take to go all the way.
The number of moves required to move along the unitypackage path
In addition, when we play the game, we don’t care how the path search algorithm finds the way. We want to see the requested path immediately. At the moment, we can be sure that the algorithm works, so let's get rid of the search visualization.
For a slow passage through the algorithm, we used corutin. We don’t need to do this anymore, so we’ll get rid of calls
Since we no longer use it
Instant results
Now we can get the paths instantly, but how fast are they calculated? Short paths appear almost immediately, but long paths on large maps may seem a bit slow.
Let's measure how much time it takes to find and display the path. We can use a profiler to determine the search time, but this is a little too much and creates additional costs. Let's use instead
Right before the search, create a new stopwatch and start it. After the search is complete, stop stopwatch and display the elapsed time in the console.
Let's choose the worst case for our algorithm - a search from the lower left to the upper right corner of a large map. The worst thing is a uniform map, because the algorithm will have to process all 4,800 map cells.
Search in the worst case The time
spent searching for it can be different, because the Unity editor is not the only process running on your machine. So test it several times to get an understanding of average duration. In my case, the search takes about 45 milliseconds. This is not very much and corresponds to 22.22 paths per second; denote this as 22 pps (paths per second). This means that the frame rate of the game will also decrease by a maximum of 22 fps in that frame when this path is calculated. And this is without taking into account all other work, for example, rendering the frame itself. That is, we get a fairly large decrease in frame rate, it will drop to 20 fps.
When performing such a performance test, you need to consider that the performance of the Unity editor will not be as high as the performance of the finished application. If I perform the same test with the assembly, then on average it will take only 15 ms. That is 66 pps, which is much better. Nevertheless, this is still a large part of the resources allocated per frame, so the frame rate will become lower than 60 fps.
We can make a simple optimization - perform a search only when it is needed. While we initiate a new search in each frame in which the mouse button is held down. Therefore, the frame rate will be constantly underestimated when dragging and dropping. We can avoid this by initiating a new search in
Displaying travel marks is a rather expensive operation, especially because we use an unoptimized approach. Performing this operation for all cells will definitely slow down the execution. So let's skip labeling in
We need to see this information only for the path found. Therefore, after reaching the end point, we will calculate the course and set the labels of only those cells that are on the way.
Displaying labels for path cells only
Now we include only cell labels between the start and the end. But the end point is the most important thing, we must also set a label for it. You can do this by starting the path cycle from the destination cell, and not from the cell in front of it. In this case, the illumination of the end point from red will change to white, so we will remove its backlighting under the cycle.
Progress information is most important for the endpoint.
After these changes, the worst-case time is reduced to 23 milliseconds in the editor and up to 6 milliseconds in the finished assembly. These are 43 pps and 166 pps - much better.
unitypackage
In the previous part, we made the search procedure smarter by implementing the A * algorithm . However, in reality we are still not performing the search in the most optimal way. In each iteration, we calculate the distances from the current cell to all its neighbors. This is true for cells that are not yet or are currently part of the search border. But the cells that have already been removed from the border, no longer need to be considered, because we have already found the shortest path to these cells. The correct implementation of A * skips these cells, so we can do the same.
How do we know if a cell has already left the border? While we can not determine this. Therefore, you need to track in what phase of the search the cell is. She has not yet been in the border, or is in it now, or is abroad. We can track this by adding to a
For example, 0 means that the cells have not yet reached, 1 - that the cell is in the border now, and 2 - that it has already been removed from the border.
In
Now we need to set the phase of the cell search when adding them to the border. The process begins with an initial cell, which is added to the border.
And also every time we add a neighbor to the border.
Until now, to verify that the cell has not yet been added to the border, we used a distance equal to
This means that we no longer need to reset cell distances before searching, that is, we will have to do less work, which is good.
When a cell is removed from the boundary, we denote this by an increase in its search phase. This puts her beyond the current border and before the next.
Now we can skip cells removed from the border, avoiding pointless calculation and comparison of distances.
At this point, our algorithm still produces the same results, but more efficiently. On my machine, the worst-case search takes 20 ms in the editor and 5 ms in the assembly.
We can also calculate how many times the cell has been processed by the algorithm, increasing the counter when calculating the distance to the cell. Previously, our algorithm in the worst case calculated 28,239 distances. In the ready-made A * algorithm, we calculate its 14,120 distances. The amount decreased by 50%. The degree of impact of these indicators on productivity depends on the costs in calculating the cost of moving. In our case, there is not much work here, so the improvement in the assembly is not very large, but it is very noticeable in the editor.
unitypackage
When initiating a new search, we first need to clear the visualization of the previous path. While we do this, turn off the selection and remove the labels from each grid cell. This is a very difficult approach. Ideally, we need to discard only those cells that were part of the previous path.
Let's start by completely removing the visualization code from
To report that
When the path is found, we need to remember it. Thanks to this, we will be able to clean it in the future. Therefore, we will track the endpoints and whether there is a path between them.
We can use the search data we recorded to visualize the path again. Let's create a new method for this
Call this method in
We see the path again, but now it is not moving away. To clear it, create a method
Using this method, we can clear the visualization of the old path by visiting only the necessary cells, the size of the map is no longer important. We will call it in
In addition, we will clear the path when creating a new map.
And also before loading another card.
The path visualization is cleared again, as before this change. But now we are using a more efficient approach, and in the worst case of the search, the time has decreased to 14 milliseconds. Enough serious improvement only due to more intelligent cleaning. Assembly time decreased to 3 ms, which is 333 pps. Thanks to this, the search for paths is exactly applicable in real time.
Now that we have made a quick search for paths, we can remove the temporary debugging code.
unitypackage
Now that we’ve figured out how to search for a path, let's place the squads on the map.
Reinforcements arrived
So far we have dealt only with cells and their fixed objects. Units differ from them in that they are mobile. A squad can mean anything of any scale, from one person or vehicle to an entire army. In this tutorial, we restrict ourselves to a simple generalized type of unit. After that, we will move on to supporting combinations of several types of units.
To work with squads, create a new type of component
Create an empty game object with this component, which should become a prefab. This will be the root object of the squad.
Prefab squad.
Add a 3D model symbolizing the detachment as a child object. I used a simple scaled cube that I created blue material for. The root object determines the ground level of the detachment, therefore, we accordingly displace the child element.
Child cube element
Add a collider to the squad so that it is easier to select in the future. The collider of the standard cube is quite suitable for us, just make the collider fit in one cell.
Since we do not have gameplay yet, the creation of units takes place in the editing mode. Therefore, this should be addressed
Connecting the prefab
When creating units, we will place them on the cell under the cursor. There
Now we can use this method in
Next, add a new method
To keep the hierarchy clean, let's use the grid as the parent for all the game objects in the squads.
The easiest way to add
Created instance of squad
Now we can create units, but they appear at the origin of the map. We need to put them in the right place. For this, it is necessary that the troops be aware of their position. Therefore, we add to the
Now I
Squads on the map
So far, all units have the same orientation, which looks rather unnatural. To revive them, add to the
In
Different unit orientations
Units look good if they are not created in one cell. In this case, we get a cluster of strange looking cubes.
Overlaid units
Some games allow the placement of several units in one place, others do not. Since it’s easier to work with one squad per cell, I will choose this option. This means that we should create a new squad only when the current cell is not occupied. So that you can find out, add to the
We use this property in
Now it
Initially, units are placed correctly, but everything can change if their cells are edited later. If the height of the cell changes, then the unit occupying it will either hang above it or plunge into it.
Hanging and drowned squads
The solution is to check the squad position after making changes. To do this, add the method to
We must coordinate the position of the detachment when updating the cell, what happens when the methods
In addition to creating units, it would be useful to destroy them. Therefore, add to the
Please note, to get to the squad, we go through the cell. To interact with the squad, just move the mouse over its cell. Therefore, for this to work, the squad does not have to have a collider. However, adding a collider makes it easier to select because it blocks the rays that would otherwise collide with the cell behind the squad.
Let's
In the case when we create and destroy several units, let's be careful and clear the property when removing the unit. That is, we explicitly clear the cell link to the squad. Add to the
We will call this method in
unitypackage
Now that we can have units on the map, we must include them in the saving and loading process. We can approach this task in two ways. The first is to record squad data when recording a cell so that the cell and squad data are mixed. The second way is to save cell and squad data separately. Although it may seem that the first approach is easier to implement, the second gives us more structured data. If we share the data, then it will be easier to work with them in the future.
To keep all units together, we need to track them. We will do this by adding to the
When creating or loading a new map, we need to get rid of all the units on the map. To simplify this process, create a method
We call this method in
Now, when creating new units, we need to add them to the list. Let's set a method for this
Now it
Add a method to remove squad and c
We call this method in
Since we are going to keep all the units together, we need to remember which cells they occupy. The most reliable way is to save the coordinates of their location. To make this possible, we add the fields X and Z to the
The method
Since it
We changed the stored data, so we will increase the version number
Since it
Since the number of units is variable, we do not have pre-existing units into which data can be loaded. We can create new instances of units before loading their data, but this will require that we
The next step is to create an instance of a new squad. However, for this we need a link to the unit’s prefab. In order not to complicate it yet, let's add a
To set this link, let's use it again
We pass the unit’s prefab.
After connecting the field, we no longer need a direct link to
Now we can create an instance of the new squad in
In the end,
Of course, this will work only for save files with version no lower than 2, in younger versions there are no units to load.
Now we can correctly upload version 2 files, so in
unitypackage
Squads are mobile, so we must be able to move them around the map. We already have a path search code, but so far we have tested it only for arbitrary places. Now we need to remove the old test UI and create a new UI for squad management.
Moving units along paths is part of the gameplay, it does not apply to the map editor. Therefore, we will get rid
After removing this code, it no longer makes sense to leave the editor active when we are not in edit mode. Therefore, instead of a mode tracking field, we can simply enable or disable the component
Since by default we are not in map editing mode, in Awake we will disable the editor.
Use raycast to search for the current cell under the cursor is necessary when editing the map, and to manage units. Perhaps in the future it will be useful to us for something else. Let's move the raycasting logic from
To control the game mode UI, we will use a new component. While he will only deal with the selection and movement of units. Create a new component type for it
Add this component to the new game object in the UI hierarchy. He does not have to have his own object, but it will be obvious to us that there is a separate UI for the game.
Game UI Object
Add a
Add the game UI method with the event list of the edit mode switch. This will mean that when the player changes the mode, both methods are called.
Several event methods.
Depending on the situation,
Create a method
When updating the current cell, we may need to find out if it has changed. Force to
Before moving a squad, it must be selected and tracked. Therefore, add a field
When we try to make a selection, we need to start by updating the current cell. If the current cell is then the unit occupying this cell becomes the selected unit. If there is no unit in the cell, then no unit is selected. Let's create a method for this
We realize the choice of units with a simple click of the mouse. Therefore, we add a method
At this stage, we learned how to select one unit at a time with the click of a mouse. When you click on an empty cell, the selection of any unit is removed. But while we do not receive any visual confirmation of this.
When a unit is selected, we can use its location as a starting point for finding a path. To activate this, we will not require another click of the mouse button. Instead, we will automatically find and show the path between the squad position and the current cell. We will always do this in
Please note that we should not find a new path every time we update, but only when the current cell changes.
Finding a path for a squad
Now we see the paths that appear when you move the cursor after selecting a squad. Thanks to this, it is obvious which unit is selected. However, the paths are not always cleared correctly. First, let's clear the old path if the cursor is outside the map.
Of course, this requires that it
Secondly, we will clear the old path when choosing a detachment.
Finally, we will clear the path when changing the editing mode.
We cannot always find the way, because sometimes it is impossible to reach the final cell. This is normal. But sometimes the final cell itself is unacceptable. For example, we decided that paths cannot include underwater cells. But it may depend on the unit. Let's add to a
In addition, we allowed only one unit to stand in the cell. Therefore, the final cell will not be valid if it is busy.
We use this method in
If we have a valid path, then we are able to move the squad to the end point.
To move a squad, add to the
Let's use the mouse button 1 (right click) to submit the command. We will check this if a detachment is selected. If the button is not pressed, then we search for the path.
Now we can move units! But sometimes they refuse to find a way to some cells. In particular, to those cells in which the detachment used to be. This happens because it
Finding the way now works correctly, and units can teleport on the map. Although they cannot move to cells that already have a squad, detachments standing in the way are ignored.
Units on the way are ignored.
Units of the same faction can usually move through each other, but so far we have no factions. Therefore, let's consider all the units as disconnected from each other and blocking the paths. This can be implemented by skipping busy cells in
Avoid detachments
unitypackage
In this part, we will force units instead of teleportation to move along the tracks.
Squads on the way
In the previous part, we added units and the ability to move them. Although we used the search for the path to determine the valid endpoints, after giving the command, the troops simply teleported to the final cell. To actually follow the found path, we need to track this path and create an animation process that forces the squad to move from cell to cell. Since looking at the animations it is difficult to notice how the squad moved, we also visualize the path traveled with the help of gizmos. But before we move on, we need to fix the error.
Due to an oversight, we incorrectly calculate the course at which the cell will be reached. Now we determine the course by dividing the total distance by the squad speed
, and discarding the remainder. The error occurs when to get into the cell you need to spend exactly all the remaining movement points per move.
For example, when each step costs 1, and the speed is 3, then we can move three cells per turn. However, with existing calculations, we can only take two steps in the first move, because for the third step
.
The summed costs of moving with incorrectly defined moves, speed 3
For the correct calculation of moves we need to move the border one step from the initial cell. We can do this by reducing the distance by 1 before calculating the move. Then the move for the third step will be
Correct moves
We can do this by changing the calculation formula to
. We’ll make this change to
We also change the marks of the moves.
Note that with this approach, the initial cell path is −1. This is normal, because we do not display it, and the search algorithm remains operational.
Moving along the path is the task of the squad. In order for him to do this, he needs to know the way. We have this information
The list is filled by following the link path from the final cell to the initial one, as is done when visualizing the path.
In this case, we need the whole path, which includes the initial cell.
Now we have the path in the reverse order. We can work with him, but it will not be very intuitive. Let's flip the list so that it goes from beginning to end.
Now we can add to the
To request movement, we change it
Before we start animating the squad, let's check that the paths are correct. We will do this by ordering to
Add a method
The easiest way to show the path is to draw a gizmo sphere for each cell of the path. A sphere with a radius of 2 units is suitable for us.
Since we will show the paths for the detachment, we will be able to simultaneously see all of its last paths.
Gizmos display the last paths traveled.
In order to better show the cell connections, we draw several spheres in a loop on a line between the previous and current cells. To do this, we need to start the process from the second cell. Spheres can be arranged using linear interpolation with an increment of 0.1 units, so that we get ten spheres per segment.
More obvious ways
You can use the same method to move units. Let's create a coroutine for this. Instead of drawing a gizmo, we will set the position of the squad. Instead of incrementing, we will use 0.1 time delta, and we will perform yield for each iteration. In this case, the squad will move from one cell to the next in one second.
Let's start coroutine at the end of the method
Moving one cell per second is pretty slow. The player during the game will not want to wait so long. You can make the squad move speed a configuration option, but for now, let's use a constant. I assigned her a value of 4 cells per second; it's pretty fast, but lets notice what is happening.
Just as we can visualize several paths simultaneously, we can make several units travel at the same time. From the point of view of the game state, the movement is still teleportation, the animations are exclusively visual. Units instantly occupy the final cell. You can even find ways and start a new move before they arrive. In this case, they are visually teleported to the beginning of a new path. This can be avoided by blocking units or even the entire UI while they are moving, but such a quick reaction is quite convenient when developing and testing movements.
Moving units.
One of the drawbacks of corutin is that they do not “survive” when recompiled in Play mode. Although the game state is always true, this can lead to squads getting stuck somewhere in their last path if recompilation is started while they are still moving. To mitigate the consequences, let's make sure that, after recompilation, the units are always in the correct position. This can be done by updating their position in
unitypackage
The movement from the center to the center of the cell looks too mechanistic and creates sharp changes in direction. For many games, this will be normal, but unacceptable if you need at least a slightly realistic movement. So let's change the movement to make it look a little more organic.
The squad begins its journey from the center of the cell. It passes to the middle of the cell edge, and then enters the next cell. Instead of moving toward the center, he can head straight for the next edge that he must cross. In fact, the unit will cut the path when it needs to change direction. This is possible for all cells except the end points of the path.
Three ways to move from edge to edge
Let's adapt
To reach the center of the end cell, we need to use the cell position as the last point, not the edge. You can add verification of this case to the loop, but it is such a simple code that it will be more obvious to simply duplicate the code and slightly change it.
Rib-based
paths The resulting paths are less like zigzags, and the maximum turning angle is reduced from 120 ° to 90 °. This can be considered an improvement, so we apply the same changes in coroutine
Moving with a changing speed
After cutting the angles, the length of the path segments became dependent on the change in direction. But we set the speed in cells per second. As a result, the detachment speed changes randomly.
Instantaneous changes in direction and speed when crossing cell boundaries look ugly. Better use a gradual change of direction. We can add support for this by forcing troops to follow along curves rather than straight lines. You can use Bezier curves for this. In particular, we can take quadratic Bezier curves at which the center of the cells will be the middle control points. In this case, the tangents of adjacent curves will be mirror images of each other, that is, the entire path will turn into a continuous smooth curve.
Curves from edge to edge
Create an auxiliary class
where 
, 
and 
Are the control points, and t is the interpolator.
To show the curve path in
In the start and end cells, instead of the end and midpoints, we can simply use the center of the cell.
Paths created using Bezier curves A curved
path looks much better. We apply the same changes to
We move along the curves. The
animation also became smooth, even when the speed of the detachment is unstable. Since the tangents of the curve of the adjacent segments coincide, the speed is continuous. The change in speed occurs gradually and happens when a detachment passes through the cell, slowing down when changing direction. If he goes straight, then the speed remains constant. In addition, the squad begins and ends its journey at zero speed. This mimics the natural movement, so leave it like that.
Up to this point, we started iterating over each of the segments from 0, continuing until we reach 1. This works fine when increasing by a constant value, but our iteration depends on the time delta. When the iteration over one segment is completed, we are likely to exceed 1 by some amount, depending on the delta of time. This is invisible at high frame rates, but can lead to jerks at low frame rates.
To avoid time loss, we need to transfer the remaining time from one segment to the next. This can be done by tracking
If we are already doing this, let's make sure that the time delta is taken into account at the beginning of the path. This means that we will begin to move immediately, and will not stand idle for one frame.
In addition, we do not finish exactly at the point in time when the path should end, but moments before. Here, the difference may also depend on the frame rate. Therefore, let's make the squad complete the path exactly at the end point.
unitypackage
The units began to move along a smooth curve, but they did not change orientation in accordance with the direction of movement. As a result, they seem to glide. To make the movement look like a real movement, we need to rotate them.
As in the Curves and Splines tutorial , we can use the derivative of the curve to determine the orientation of the unit. The formula for the derivative of a quadratic Bezier curve:
. Add to the
The derivative vector is located on one straight line with the direction of motion. We can use the method
In contrast to the position of the detachment, the non-ideality of its orientation at the end of the path is not important. however, we need to ensure that its orientation corresponds to the final rotation. To do this, after completion, we equate its orientation to its rotation in Y.
Now the units are looking exactly in the direction of movement, both horizontally and vertically. This means that they will lean forward and backward, descending from the slopes and climbing them. To ensure that they always stand straight, we force the component Y of the direction vector to zero before using it to determine the rotation of the unit.
Looking forward while moving
Throughout the path, the units are looking forward, but before starting to move, they can look in the other direction. In this case, they instantly change their orientation. It will be better if they turn in the direction of the path before the start of movement.
Looking in the right direction can be useful in other situations, so let's create a method
So that the detachment actually turns, we will turn the method into another corutin that will rotate it at a constant speed. The turning speed can also be adjusted, but we will use the constant again. The rotation should be fast, about 180 ° per second.
It is not necessary to tinker with acceleration of the turn, because it is imperceptible. It will be enough for us to simply interpolate between the two orientations. Unfortunately, this is not as simple as in the case of two numbers, because the angles are circular. For example, a transition from 350 ° to 10 ° should result in a 20 ° clockwise rotation, but simple interpolation will force a 340 ° rotation in a counterclockwise direction.
The easiest way to create a correct rotation is to interpolate between two quaternions using spherical interpolation. This will lead to the shortest turn. To do this, we get the quaternions of the beginning and the end, and then make a transition between them using
This will work, but interpolation always goes from 0 to 1, regardless of the angle of rotation. To ensure uniform angular velocity, we need to slow down the interpolation as the angle of rotation increases.
Knowing the angle, we can completely skip the turn if it turns out to be zero.
Now we can add the unit’s rotation in
Если проверить работу кода, то отряд телепортируется в конечную ячейку, повернётся там, а затем телепортируется обратно к началу пути и начнёт оттуда движение. Так происходит, потому что мы присваиваем значение свойству
Поворот перед движением
Получив нужное нам движение, мы можем избавиться от метода
Так как нам больше не нужно запоминать, по какому пути мы двигались, то в конце
unitypackage
Parts 4-7: bumps, rivers and roads;
Parts 8-11: water, landforms and fortress walls;
Parts 12-15: saving and loading, textures, distances;
Parts 16-19: path finding, player squads, animations
Parts 20-23: fog of war, map exploration, procedural generation
Parts 24-27: water cycle, erosion, biomes, cylindrical map
Part 16: finding the way
- Highlight cells
- Select a search target
- Find the shortest path
- Create a priority queue
After calculating the distances between the cells, we proceeded to finding the paths between them.
Starting with this part, hexagon map tutorials will be created in Unity 5.6.0. It should be noted that in 5.6 there is a bug that destroys arrays of textures in assemblies for several platforms. You can get around it by including Is Readable in the texture array inspector .
Planning a trip
Highlighted cells
To search the path between two cells, we first need to select these cells. It’s more than just choosing one cell and monitoring the search on the map. For example, we will first select the initial cell, and then the final one. In this case, it would be convenient for them to become highlighted. Therefore, let's add such functionality. Until we create a sophisticated or efficient way of highlighting, we just create something to help us with the development.
Outline texture
One simple way to select cells is to add a path to them. The easiest way to do this is with a texture containing a hexagonal outline. Here you can download such a texture. It is transparent except for the white outline of the hexagon. Having made it white, in the future we will be able to colorize it as we need.
The cell outline on a black background.
Import the texture and set its Texture Type to Sprite . Her Sprite Mode will be set to Single with default settings. Since this is an exceptionally white texture, we do not need to convert to sRGB . The alpha channel indicates transparency, so enable Alpha is Transparency . I also set the Filter Mode texture to Trilinear , because otherwise the mip transitions for the paths might become too noticeable.
Texture Import Options
One sprite per cell
The fastest way is to add a possible contour to the cells, adding each own sprite. Create a new game object, add the Image component ( Component / UI / Image ) to it and assign it our outline sprite. Then insert the Hex Cell Label prefab instance into the scene, make the sprite object a child of it, apply the changes to the prefab, and then get rid of the prefab.
Prefab Selection Child Element
Now each cell has a sprite, but it will be too large. To make the contours match the centers of the cells, change the Width and Height of the transform component of the sprite to 17.
Selection sprites partially hidden by a relief
Drawing on top of everything
Since the contour is superimposed on the area of the edges of the cells, it often appears under the geometry of the relief. Because of this, part of the circuit disappears. This can be avoided by slightly raising the sprites vertically, but not in the case of breaks. Instead, we can do the following: always draw sprites on top of everything else. To do this, create your own sprite shader. It will be enough for us to copy the standard Unity sprite shader and make a couple of changes to it.
Shader "Custom/Highlight" {
Properties {
[PerRendererData] _MainTex ("Sprite Texture", 2D) = "white" {}
_Color ("Tint", Color) = (1,1,1,1)
[MaterialToggle] PixelSnap ("Pixel snap", Float) = 0
[HideInInspector] _RendererColor ("RendererColor", Color) = (1,1,1,1)
[HideInInspector] _Flip ("Flip", Vector) = (1,1,1,1)
[PerRendererData] _AlphaTex ("External Alpha", 2D) = "white" {}
[PerRendererData] _EnableExternalAlpha ("Enable External Alpha", Float) = 0
}
SubShader {
Tags {
"Queue"="Transparent"
"IgnoreProjector"="True"
"RenderType"="Transparent"
"PreviewType"="Plane"
"CanUseSpriteAtlas"="True"
}
Cull Off
ZWrite Off
Blend One OneMinusSrcAlpha
Pass {
CGPROGRAM
#pragma vertex SpriteVert
#pragma fragment SpriteFrag
#pragma target 2.0
#pragma multi_compile_instancing
#pragma multi_compile _ PIXELSNAP_ON
#pragma multi_compile _ ETC1_EXTERNAL_ALPHA
#include "UnitySprites.cginc"
ENDCG
}
}
}The first change is that we ignore the depth buffer, making the Z-test always succeed.
ZWrite Off
ZTest AlwaysThe second change is that we are rendering after the rest of the transparent geometry. Enough to add 10 to the transparency queue.
"Queue"="Transparent+10"Create a new material that this shader will use. We can ignore all its properties, adhering to the default values. Then make the sprite prefab use this material.
We use our own sprite material.
Now the selection contours are always visible. Even if the cell is hidden under a higher relief, its outline will still be drawn on top of everything else. It may not look beautiful, but the selected cells will always be visible, which is useful for us.
Ignore the depth buffer
Selection control
We do not want all cells to be highlighted at the same time. In fact, initially they should all be unselected. We can implement this by disabling the Image component of the Highlight prefab object .
Disabled Image component
To enable cell selection, add to the
HexCellmethod EnableHighlight. It should take the only child of its own uiRectand include its Image component. We will also create a method DisableHighlight. public void DisableHighlight () {
Image highlight = uiRect.GetChild(0).GetComponent![]()
();
highlight.enabled = false;
}
public void EnableHighlight () {
Image highlight = uiRect.GetChild(0).GetComponent![]()
();
highlight.enabled = true;
}Finally, we can specify the color so that when turned on, give the backlight a hue.
public void EnableHighlight (Color color) {
Image highlight = uiRect.GetChild(0).GetComponent![]()
();
highlight.color = color;
highlight.enabled = true;
}unitypackage
Finding the way
Now that we can select the cells, we need to move on and select two cells, and then find the path between them. First we need to select the cells, then restrict the search to a path between them, and finally show this path.
Search start
We need to select two different cells, the start and end points of the search. Suppose that to select the initial search cell, hold the left Shift key while clicking the mouse. In this case, the cell is highlighted in blue. We need to save the link to this cell for further search. In addition, when choosing a new starting cell, the selection of the old one must be disabled. Therefore, add to the
HexMapEditorfield searchFromCell. HexCell previousCell, searchFromCell;Inside,
HandleInputwe can use the Input.GetKey(KeyCode.LeftShift)Shift key to test it while holding it down. if (editMode) {
EditCells(currentCell);
}
else if (Input.GetKey(KeyCode.LeftShift)) {
if (searchFromCell) {
searchFromCell.DisableHighlight();
}
searchFromCell = currentCell;
searchFromCell.EnableHighlight(Color.blue);
}
else {
hexGrid.FindDistancesTo(currentCell);
}Where to look
Search endpoint
Instead of looking for all the distances to a cell, we are now looking for a path between two specific cells. Therefore, rename it
HexGrid.FindDistancesToto HexGrid.FindPathand give it a second parameter HexCell. Also change the method Search. public void FindPath (HexCell fromCell, HexCell toCell) {
StopAllCoroutines();
StartCoroutine(Search(fromCell, toCell));
}
IEnumerator Search (HexCell fromCell, HexCell toCell) {
for (int i = 0; i < cells.Length; i++) {
cells[i].Distance = int.MaxValue;
}
WaitForSeconds delay = new WaitForSeconds(1 / 60f);
List frontier = new List();
fromCell.Distance = 0;
frontier.Add(fromCell);
…
} Now,
HexMapEditor.HandleInputshould cause the modified method, using as arguments searchFromCelland currentCell. In addition, we can search only when we know from which cell to search. And we do not have to bother to search if the start and end points coincide. if (editMode) {
EditCells(currentCell);
}
else if (Input.GetKey(KeyCode.LeftShift)) {
…
}
else if (searchFromCell && searchFromCell != currentCell) {
hexGrid.FindPath(searchFromCell, currentCell);
}Turning to the search, we first need to get rid of all previous selections. Therefore, we will force to
HexGrid.Searchturn off the selection when resetting distances. Since this also turns off the illumination of the initial cell, then turn it on again. At this stage, we can also highlight the end point. Let's make her red. IEnumerator Search (HexCell fromCell, HexCell toCell) {
for (int i = 0; i < cells.Length; i++) {
cells[i].Distance = int.MaxValue;
cells[i].DisableHighlight();
}
fromCell.EnableHighlight(Color.blue);
toCell.EnableHighlight(Color.red);
…
}Endpoints of a potential path
Limit search
At this point, our search algorithm still calculates the distances to all cells that are reachable from the starting cell. But we don’t need it anymore. We can stop as soon as we find the final distance to the final cell. That is, when the current cell is finite, we can exit the algorithm loop.
while (frontier.Count > 0) {
yield return delay;
HexCell current = frontier[0];
frontier.RemoveAt(0);
if (current == toCell) {
break;
}
for (HexDirection d = HexDirection.NE; d <= HexDirection.NW; d++) {
…
}
}Stop at the end point
What happens if the endpoint cannot be reached?
Then the algorithm will continue to work until it finds all reachable cells. Without the possibility of a premature exit, it will work as an old method
FindDistancesTo.Path display
We can find the distance between the beginning and the end of the path, but do not yet know what the real path will be. To find it, you need to track how each cell is reached. But how to do that?
When adding a cell to the border, we do this because it is a neighbor of the current cell. The one exception is the starting cell. All other cells have been reached through the current cell. If we keep track of which cell each cell was reached from, we get a network of cells as a result. More precisely, a tree-like network, the root of which is the starting point. We can use it to build the path after reaching the end point.
A tree-like network that describes the paths to the center
We can save this information by adding
HexCellanother cell to the link. We do not need to serialize this data, so we use the standard property for this. public HexCell PathFrom { get; set; }We
HexGrid.Searchset the PathFromcurrent cell as the neighbor value when adding it to the border. In addition, we need to change this link when we find a shorter way to the neighbor. if (neighbor.Distance == int.MaxValue) {
neighbor.Distance = distance;
neighbor.PathFrom = current;
frontier.Add(neighbor);
}
else if (distance < neighbor.Distance) {
neighbor.Distance = distance;
neighbor.PathFrom = current;
}Having reached the end point, we can visualize the path by following these links back to the starting cell and select them.
if (current == toCell) {
current = current.PathFrom;
while (current != fromCell) {
current.EnableHighlight(Color.white);
current = current.PathFrom;
}
break;
}The path found
It is worth considering that often there are several shortest paths. The one found depends on the processing order of the cells. Some paths may look good, others may be bad, but there is never a shorter path. We will come back to this later.
Change start of search
After selecting the start point, changing the end point will trigger a new search. The same thing should happen when choosing a new starting cell. To make this possible,
HexMapEditorit must also remember the endpoint. HexCell previousCell, searchFromCell, searchToCell;Using this field, we can also initiate a new search when choosing a new beginning.
else if (Input.GetKey(KeyCode.LeftShift)) {
if (searchFromCell) {
searchFromCell.DisableHighlight();
}
searchFromCell = currentCell;
searchFromCell.EnableHighlight(Color.blue);
if (searchToCell) {
hexGrid.FindPath(searchFromCell, searchToCell);
}
}
else if (searchFromCell && searchFromCell != currentCell) {
searchToCell = currentCell;
hexGrid.FindPath(searchFromCell, searchToCell);
}In addition, we need to avoid equal starting and ending points.
if (editMode) {
EditCells(currentCell);
}
else if (
Input.GetKey(KeyCode.LeftShift) && searchToCell != currentCell
) {
…
}unitypackage
Smarter Search
Although our algorithm finds the shortest path, it spends a lot of time exploring points that obviously will not become part of this path. At least it’s obvious to us. The algorithm cannot look down on the map; it cannot see that a search in some directions will be meaningless. He prefers to move on the roads, despite the fact that they are heading in the opposite direction from the end point. Is it possible to make the search smarter?
At the moment, when choosing the cell to be processed next, we consider only the distance from the cell to the beginning. If we want to do smarter, then we must also consider the distance to the end point. Unfortunately, we do not know him yet. But we can create an estimate of the remaining distance. Adding this estimate to the distance to the cell gives us an understanding of the total length of the path passing through this cell. Then we can use it to prioritize cell searches.
Search Heuristics
When we use estimation or guesswork instead of exactly known data, this is called using search heuristics. This heuristic represents the best guess of the distance left. We must determine this value for each cell that we are searching for, so we add an
HexCellinteger property for it . We do not need to serialize it, so another standard property will suffice. public int SearchHeuristic { get; set; }How do we make an assumption about the remaining distance? In the most ideal case, we will have a road leading straight to the end point. If so, then the distance is equal to the unchanged distance between the coordinates of this cell and the final cell. Let's take advantage of this in our heuristic.
Since heuristics does not depend on a previously traveled path, it is constant in the search process. Therefore, we need to calculate it only once it
HexGrid.Searchadds a cell to the border. if (neighbor.Distance == int.MaxValue) {
neighbor.Distance = distance;
neighbor.PathFrom = current;
neighbor.SearchHeuristic =
neighbor.coordinates.DistanceTo(toCell.coordinates);
frontier.Add(neighbor);
}Search Priority
From now on, we will determine the priority of the search based on the distance to the cell plus its heuristics. Let's add values to this
HexCellproperty. public int SearchPriority {
get {
return distance + SearchHeuristic;
}
}For this to work, change it
HexGrid.Searchso that it uses this property to sort the border. frontier.Sort(
(x, y) => x.SearchPriority.CompareTo(y.SearchPriority)
);Search without heuristics and with heuristics
Valid Heuristic
Thanks to the new search priorities, we will actually visit fewer cells as a result. However, on a uniform map, the algorithm still processes cells that are in the wrong direction. This is because, by default, the costs for each move step are 5, and the heuristic per step adds only 1. That is, the influence of the heuristic is not very strong.
If the costs of moving on all the cards are the same, then we can use the same costs when determining the heuristic. In our case, this will be the current heuristic multiplied by 5. This will significantly reduce the number of processed cells.
We use heuristics × 5
However, if there are roads on the map, then we can overestimate the remaining distance. As a result, the algorithm can make mistakes and create a path that is actually not the shortest.
Reevaluated and valid heuristics
To ensure that the shortest path is found, we need to make sure that we never overestimate the remaining distance. This approach is called valid heuristics. Since the minimum cost of moving is 1, we have no choice but to use the same costs in determining the heuristic.
Strictly speaking, it is quite normal to use even lower costs, but this will only make the heuristic weaker. The minimum possible heuristic is zero, which gives us just Dijkstra's algorithm. With a nonzero heuristic, the algorithm is called A * (pronounced "A star").
Why is it called A *?
Идея добавления эвристики в алгоритм Дейкстры впервые была предложена Нильсом Нильссоном. Он назвал свой вариант A1. Позже Бертрам Рафаэль придумал лучшую версию, которую он назвал A2. Затем Питер Харт доказал, что при хорошей эвристике A2 оптимален, то есть более хорошей версии быть не может. Это заставило его назвать алгоритм A*, чтобы показать, что его невозможно будет улучшить, то есть A3 или A4 не появятся. Так что да, алгоритм A* — это лучшее, что мы можем получить, но он хорош настолько, насколько хороша его эвристика.
unitypackage
Очередь с приоритетом
Although A * is a good algorithm, our implementation is not so effective, because we use a list to store the border, which needs to be sorted at each iteration. As mentioned in the previous part, we need a priority queue, but its standard implementation does not exist. Therefore, let's create it yourself.
Our turn should support the operation of setting and exclusion from the queue based on priority. It should also support changing the priority of a cell already in the queue. Ideally, we implement it, minimizing the search for sorting and allocated memory. In addition, it should remain simple.
Create your own queue
Create a new class
HexCellPriorityQueuewith the required common methods. We use a simple list to track the contents of a queue. In addition, we add a method Clearto reset the queue so that it can be reused.using System.Collections.Generic;
public class HexCellPriorityQueue {
List list = new List();
public void Enqueue (HexCell cell) {
}
public HexCell Dequeue () {
return null;
}
public void Change (HexCell cell) {
}
public void Clear () {
list.Clear();
}
} We store cell priorities in the cells themselves. That is, before adding a cell to the queue, its priority must be set. But in the event of a priority change, it will probably be useful to know what the old priority was. So let's add this in
Changeas a parameter. public void Change (HexCell cell, int oldPriority) {
}It is also useful to know how many cells are in the queue, so add a property for this
Count. Just use the field for which we will perform the corresponding increment and decrement. int count = 0;
public int Count {
get {
return count;
}
}
public void Enqueue (HexCell cell) {
count += 1;
}
public HexCell Dequeue () {
count -= 1;
return null;
}
…
public void Clear () {
list.Clear();
count = 0;
}Add to Queue
When a cell is added to the queue, let's first use its priority as an index, treating the list as a simple array.
public void Enqueue (HexCell cell) {
count += 1;
int priority = cell.SearchPriority;
list[priority] = cell;
}However, this only works if the list is long enough, otherwise we will go beyond the borders. You can avoid this by adding empty items to the list until it reaches the required length. These empty elements do not reference the cell, so they can be created by adding to the list
null. int priority = cell.SearchPriority;
while (priority >= list.Count) {
list.Add(null);
}
list[priority] = cell;The list with holes
But this is how we store only one cell per priority, and most likely there will be several. To track all cells with the same priority, we need to use another list. Although we can use a real list for each priority, we can also add to the
HexCellproperty to link them together. This allows us to create a chain of cells called a linked list. public HexCell NextWithSamePriority { get; set; }To create a chain, let's
HexCellPriorityQueue.Enqueuemake the newly added cell refer to the current value with the same priority before deleting it. cell.NextWithSamePriority = list[priority];
list[priority] = cell;List of linked lists
Remove from queue
To get a cell from a priority queue, we need to access the linked list at the lowest non-empty index. Therefore, we will go around the list in a loop until we find it. If we do not find, then the queue is empty and we return
null. From the found chain, we can return any cell, because they all have the same priority. The easiest way is to return the cell from the beginning of the chain.
public HexCell Dequeue () {
count -= 1;
for (int i = 0; i < list.Count; i++) {
HexCell cell = list[i];
if (cell != null) {
return cell;
}
}
return null;
}To keep the link to the remaining chain, use the next cell with the same priority as the new start. If at this priority level there was only one cell, then the element becomes
nulland will be skipped in the future. if (cell != null) {
list[i] = cell.NextWithSamePriority;
return cell;
}Minimum tracking
This approach works, but iterates through the list each time a cell is received. We cannot avoid finding the smallest nonempty index, but we are not required to start from scratch every time. Instead, we can track the minimum priority and start the search with it. Initially, the minimum is essentially equal to infinity.
int minimum = int.MaxValue;
…
public void Clear () {
list.Clear();
count = 0;
minimum = int.MaxValue;
}When adding a cell to the queue, we change the minimum as necessary.
public void Enqueue (HexCell cell) {
count += 1;
int priority = cell.SearchPriority;
if (priority < minimum) {
minimum = priority;
}
…
}And when withdrawing from the queue, we use at least the list for iterations, and do not start from scratch.
public HexCell Dequeue () {
count -= 1;
for (; minimum < list.Count; minimum++) {
HexCell cell = list[minimum];
if (cell != null) {
list[minimum] = cell.NextWithSamePriority;
return cell;
}
}
return null;
}This significantly reduces the amount of time it takes to bypass in the priority list loop.
Change Priorities
When changing the priority of a cell, it must be removed from the linked list of which it is a part. To do this, we need to follow the chain until we find it.
Let's start by declaring that the head of the old priority list will be the current cell, and we will also track the next cell. We can immediately take the next cell, because we know that there is at least one cell by this index.
public void Change (HexCell cell, int oldPriority) {
HexCell current = list[oldPriority];
HexCell next = current.NextWithSamePriority;
}If the current cell is a changed cell, then this is the head cell and we can cut it off as if we had pulled it out of the queue.
HexCell current = list[oldPriority];
HexCell next = current.NextWithSamePriority;
if (current == cell) {
list[oldPriority] = next;
}If this is not the case, then we need to follow the chain until we are in the cell in front of the changed cell. It contains a link to the cell that has been modified.
if (current == cell) {
list[oldPriority] = next;
}
else {
while (next != cell) {
current = next;
next = current.NextWithSamePriority;
}
}At this point, we can remove the changed cell from the linked list, skipping it.
while (next != cell) {
current = next;
next = current.NextWithSamePriority;
}
current.NextWithSamePriority = cell.NextWithSamePriority;After deleting a cell, you need to add it again so that it appears in the list of its new priority.
public void Change (HexCell cell, int oldPriority) {
…
Enqueue(cell);
}The method
Enqueueincrements the counter, but in reality we are not adding a new cell. Therefore, in order to compensate for this, we will have to decrement the counter. Enqueue(cell);
count -= 1;Queue usage
Now we can take advantage of our priority queue at
HexGrid. This can be done with a single instance, reusable for all search operations. HexCellPriorityQueue searchFrontier;
…
IEnumerator Search (HexCell fromCell, HexCell toCell) {
if (searchFrontier == null) {
searchFrontier = new HexCellPriorityQueue();
}
else {
searchFrontier.Clear();
}
…
}Before starting the loop, the method
Searchmust first be added to the queue fromCell, and each iteration begins with the output of the cell from the queue. This will replace the old border code. WaitForSeconds delay = new WaitForSeconds(1 / 60f);
// List frontier = new List();
fromCell.Distance = 0;
// frontier.Add(fromCell);
searchFrontier.Enqueue(fromCell);
while (searchFrontier.Count > 0) {
yield return delay;
HexCell current = searchFrontier.Dequeue();
// frontier.RemoveAt(0);
…
} Change the code so that it adds and changes the neighbor. Before the change we will remember the old priority.
if (neighbor.Distance == int.MaxValue) {
neighbor.Distance = distance;
neighbor.PathFrom = current;
neighbor.SearchHeuristic =
neighbor.coordinates.DistanceTo(toCell.coordinates);
// frontier.Add(neighbor);
searchFrontier.Enqueue(neighbor);
}
else if (distance < neighbor.Distance) {
int oldPriority = neighbor.SearchPriority;
neighbor.Distance = distance;
neighbor.PathFrom = current;
searchFrontier.Change(neighbor, oldPriority);
}In addition, we no longer need to sort the border.
// frontier.Sort(
// (x, y) => x.SearchPriority.CompareTo(y.SearchPriority)
// );Search using a priority queue
As mentioned earlier, the shortest path found depends on the processing order of the cells. Our turn creates an order different from the order of the sorted list, so we can get other ways. Since we add and remove from the head of the linked list for each priority, they are more like stacks than queues. Cells added last are processed first. A side effect of this approach is that the algorithm is zigzag prone. Therefore, the likelihood of zigzag paths also increases. Fortunately, such paths usually look better, so this side effect is in our favor.
Sorted list and queue with unitypackage priority
Part 17: limited movement
- We find ways for step-by-step movement.
- Immediately display the path.
- We create a more effective search.
- We visualize only the path.
In this part, we will divide the movement into moves and speed up the search as much as possible.
Travel from several moves
Step by step movement
Strategy games that use hexagon nets are almost always turn-based. Units moving on the map have a limited speed, which limits the distance traveled in one turn.
Speed
To provide support for limited movement, we add in
HexGrid.FindPathand into the HexGrid.Searchinteger parameter speed. It determines the range of motion for one move. public void FindPath (HexCell fromCell, HexCell toCell, int speed) {
StopAllCoroutines();
StartCoroutine(Search(fromCell, toCell, speed));
}
IEnumerator Search (HexCell fromCell, HexCell toCell, int speed) {
…
}Different types of units in the game use different speeds. Cavalry is fast, infantry is slow, and so on. We do not yet have units, so for now we will use a constant speed. Let's take a value of 24. This is a fairly large value, not divisible by 5 (the default cost of moving). Add as an argument to
FindPathat HexMapEditor.HandleInputconstant speed. if (editMode) {
EditCells(currentCell);
}
else if (
Input.GetKey(KeyCode.LeftShift) && searchToCell != currentCell
) {
if (searchFromCell) {
searchFromCell.DisableHighlight();
}
searchFromCell = currentCell;
searchFromCell.EnableHighlight(Color.blue);
if (searchToCell) {
hexGrid.FindPath(searchFromCell, searchToCell, 24);
}
}
else if (searchFromCell && searchFromCell != currentCell) {
searchToCell = currentCell;
hexGrid.FindPath(searchFromCell, searchToCell, 24);
}Moves
In addition to tracking the total cost of moving along the path, we now also need to know how many moves it will take to move along it. But we do not need to store this information in each cell. It can be obtained by dividing the distance traveled by speed. Since these are integers, we will use integer division. That is, the total distances of no more than 24 correspond to the course 0. This means that the whole path can be completed in the current course. If the end point is at a distance of 30, then this must be turn 1. To get to the end point, the unit will have to spend all its movement in the current turn and in part of the next turn.
Let's determine the course of the current cell and all its neighbors inside
HexGrid.Search. The course of the current cell can be calculated only once, right before going around in the neighbor cycle. The neighbor’s move can be determined as soon as we find the distance to him. int currentTurn = current.Distance / speed;
for (HexDirection d = HexDirection.NE; d <= HexDirection.NW; d++) {
…
int distance = current.Distance;
if (current.HasRoadThroughEdge(d)) {
distance += 1;
}
else if (current.Walled != neighbor.Walled) {
continue;
}
else {
distance += edgeType == HexEdgeType.Flat ? 5 : 10;
distance += neighbor.UrbanLevel + neighbor.FarmLevel +
neighbor.PlantLevel;
}
int turn = distance / speed;
…
}Lost movement
If the neighbor’s move is greater than the current move, then we crossed the boundary of the move. If the movement necessary to reach a neighbor was 1, then everything is fine. But if moving to the next cell is more expensive, then everything becomes more complicated.
Suppose that we move along a homogeneous map, that is, to get into each cell you need 5 units of movement. Our speed is 24. After four steps, we spent 20 units from our stock of movement, and there are 4 left. In the next step, 5 units are needed again, that is, one more than the available ones. What do we need to do at this stage?
There are two approaches to this situation. The first is to allow the unit to enter the fifth cell in the current turn, even if we do not have enough movement. The second is to prohibit movement during the current move, that is, the remaining movement points cannot be used and they will be lost.
The choice of option depends on the game. In general, the first approach is more appropriate for games in which units can move only a few steps per turn, for example, for games in the Civilization series. This ensures that units can always move at least one cell per turn. If units can move many cells per turn, as in Age of Wonders or in Battle for Wesnoth, then the second option is better.
Since we use speed 24, let's choose the second approach. In order for it to start working, we need to isolate the costs of getting into the next cell before adding it to the current distance.
// int distance = current.Distance;
int moveCost;
if (current.HasRoadThroughEdge(d)) {
moveCost = 1;
}
else if (current.Walled != neighbor.Walled) {
continue;
}
else {
moveCost = edgeType == HexEdgeType.Flat ? 5 : 10;
moveCost += neighbor.UrbanLevel + neighbor.FarmLevel +
neighbor.PlantLevel;
}
int distance = current.Distance + moveCost;
int turn = distance / speed;If as a result we cross the border of the move, then first we use all the movement points of the current move. We can do this by simply multiplying the move by speed. After that, we add the cost of moving.
int distance = current.Distance + moveCost;
int turn = distance / speed;
if (turn > currentTurn) {
distance = turn * speed + moveCost;
}As a result of this, we will complete the first move in the fourth cell with 4 unused movement points. These lost points are added to the costs of the fifth cell, so its distance becomes 29, not 25. As a result, the distances are greater than before. For example, the tenth cell had a distance of 50. But now to get into it, we need to cross the borders of two moves, losing 8 movement points, that is, the distance to it now becomes 58.
Longer than expected
Since unused movement points are added to the distances to the cells, they are taken into account when determining the shortest path. The most effective way is wasting as few points as possible. Therefore, at different speeds, we can get different paths.
Showing moves instead of distances
When we play the game, we are not very interested in the distance values used to find the shortest path. We are interested in the number of moves required to reach the end point. Therefore, instead of distances, let's display the moves.
First, get rid of
UpdateDistanceLabelhis call in HexCell. public int Distance {
get {
return distance;
}
set {
distance = value;
// UpdateDistanceLabel();
}
}
…
// void UpdateDistanceLabel () {
// UnityEngine.UI.Text label = uiRect.GetComponent();
// label.text = distance == int.MaxValue ? "" : distance.ToString();
// } Instead, we will add to the
HexCellgeneral method SetLabelthat receives an arbitrary string. public void SetLabel (string text) {
UnityEngine.UI.Text label = uiRect.GetComponent();
label.text = text;
} We use this new method in
HexGrid.Searchcleaning cells. To hide cells, simply assign them null. for (int i = 0; i < cells.Length; i++) {
cells[i].Distance = int.MaxValue;
cells[i].SetLabel(null);
cells[i].DisableHighlight();
}Then we assign the neighbor’s mark the value of his move. After that, we will be able to see how many additional moves it will take to go all the way.
if (neighbor.Distance == int.MaxValue) {
neighbor.Distance = distance;
neighbor.SetLabel(turn.ToString());
neighbor.PathFrom = current;
neighbor.SearchHeuristic =
neighbor.coordinates.DistanceTo(toCell.coordinates);
searchFrontier.Enqueue(neighbor);
}
else if (distance < neighbor.Distance) {
int oldPriority = neighbor.SearchPriority;
neighbor.Distance = distance;
neighbor.SetLabel(turn.ToString());
neighbor.PathFrom = current;
searchFrontier.Change(neighbor, oldPriority);
}The number of moves required to move along the unitypackage path
Instant paths
In addition, when we play the game, we don’t care how the path search algorithm finds the way. We want to see the requested path immediately. At the moment, we can be sure that the algorithm works, so let's get rid of the search visualization.
Without corutin
For a slow passage through the algorithm, we used corutin. We don’t need to do this anymore, so we’ll get rid of calls
StartCoroutineand StopAllCoroutinesc HexGrid. Instead, we simply invoke it Searchas a regular method. public void Load (BinaryReader reader, int header) {
// StopAllCoroutines();
…
}
public void FindPath (HexCell fromCell, HexCell toCell, int speed) {
// StopAllCoroutines();
// StartCoroutine(Search(fromCell, toCell, speed));
Search(fromCell, toCell, speed);
}Since we no longer use it
Searchas coroutine, it does not need yield, so we will get rid of this operator. This means that we will also remove the declaration WaitForSecondsand change the return type of the method to void. void Search (HexCell fromCell, HexCell toCell, int speed) {
…
// WaitForSeconds delay = new WaitForSeconds(1 / 60f);
fromCell.Distance = 0;
searchFrontier.Enqueue(fromCell);
while (searchFrontier.Count > 0) {
// yield return delay;
HexCell current = searchFrontier.Dequeue();
…
}
}Instant results
Search time definition
Now we can get the paths instantly, but how fast are they calculated? Short paths appear almost immediately, but long paths on large maps may seem a bit slow.
Let's measure how much time it takes to find and display the path. We can use a profiler to determine the search time, but this is a little too much and creates additional costs. Let's use instead
Stopwatch, which is in the namespace System.Diagnostics. Since we use it only temporarily, I will not add the construct usingto the beginning of the script. Right before the search, create a new stopwatch and start it. After the search is complete, stop stopwatch and display the elapsed time in the console.
public void FindPath (HexCell fromCell, HexCell toCell, int speed) {
System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
sw.Start();
Search(fromCell, toCell, speed);
sw.Stop();
Debug.Log(sw.ElapsedMilliseconds);
}Let's choose the worst case for our algorithm - a search from the lower left to the upper right corner of a large map. The worst thing is a uniform map, because the algorithm will have to process all 4,800 map cells.
Search in the worst case The time
spent searching for it can be different, because the Unity editor is not the only process running on your machine. So test it several times to get an understanding of average duration. In my case, the search takes about 45 milliseconds. This is not very much and corresponds to 22.22 paths per second; denote this as 22 pps (paths per second). This means that the frame rate of the game will also decrease by a maximum of 22 fps in that frame when this path is calculated. And this is without taking into account all other work, for example, rendering the frame itself. That is, we get a fairly large decrease in frame rate, it will drop to 20 fps.
When performing such a performance test, you need to consider that the performance of the Unity editor will not be as high as the performance of the finished application. If I perform the same test with the assembly, then on average it will take only 15 ms. That is 66 pps, which is much better. Nevertheless, this is still a large part of the resources allocated per frame, so the frame rate will become lower than 60 fps.
Where can I see the debug log for the assembly?
Unity applications write to a log file that is saved on the system. Its location depends on the platform. To find out how to find the log files on your system, read the Unity Log Files documentation .
Search only if necessary.
We can make a simple optimization - perform a search only when it is needed. While we initiate a new search in each frame in which the mouse button is held down. Therefore, the frame rate will be constantly underestimated when dragging and dropping. We can avoid this by initiating a new search in
HexMapEditor.HandleInputonly when we are really dealing with a new endpoint. If not, then the current visible path is still valid. if (editMode) {
EditCells(currentCell);
}
else if (
Input.GetKey(KeyCode.LeftShift) && searchToCell != currentCell
) {
if (searchFromCell != currentCell) {
if (searchFromCell) {
searchFromCell.DisableHighlight();
}
searchFromCell = currentCell;
searchFromCell.EnableHighlight(Color.blue);
if (searchToCell) {
hexGrid.FindPath(searchFromCell, searchToCell, 24);
}
}
}
else if (searchFromCell && searchFromCell != currentCell) {
if (searchToCell != currentCell) {
searchToCell = currentCell;
hexGrid.FindPath(searchFromCell, searchToCell, 24);
}
}Show labels only for the path
Displaying travel marks is a rather expensive operation, especially because we use an unoptimized approach. Performing this operation for all cells will definitely slow down the execution. So let's skip labeling in
HexGrid.Search. if (neighbor.Distance == int.MaxValue) {
neighbor.Distance = distance;
// neighbor.SetLabel(turn.ToString());
neighbor.PathFrom = current;
neighbor.SearchHeuristic =
neighbor.coordinates.DistanceTo(toCell.coordinates);
searchFrontier.Enqueue(neighbor);
}
else if (distance < neighbor.Distance) {
int oldPriority = neighbor.SearchPriority;
neighbor.Distance = distance;
// neighbor.SetLabel(turn.ToString());
neighbor.PathFrom = current;
searchFrontier.Change(neighbor, oldPriority);
}We need to see this information only for the path found. Therefore, after reaching the end point, we will calculate the course and set the labels of only those cells that are on the way.
if (current == toCell) {
current = current.PathFrom;
while (current != fromCell) {
int turn = current.Distance / speed;
current.SetLabel(turn.ToString());
current.EnableHighlight(Color.white);
current = current.PathFrom;
}
break;
}Displaying labels for path cells only
Now we include only cell labels between the start and the end. But the end point is the most important thing, we must also set a label for it. You can do this by starting the path cycle from the destination cell, and not from the cell in front of it. In this case, the illumination of the end point from red will change to white, so we will remove its backlighting under the cycle.
fromCell.EnableHighlight(Color.blue);
// toCell.EnableHighlight(Color.red);
fromCell.Distance = 0;
searchFrontier.Enqueue(fromCell);
while (searchFrontier.Count > 0) {
HexCell current = searchFrontier.Dequeue();
if (current == toCell) {
// current = current.PathFrom;
while (current != fromCell) {
int turn = current.Distance / speed;
current.SetLabel(turn.ToString());
current.EnableHighlight(Color.white);
current = current.PathFrom;
}
toCell.EnableHighlight(Color.red);
break;
}
…
}Progress information is most important for the endpoint.
After these changes, the worst-case time is reduced to 23 milliseconds in the editor and up to 6 milliseconds in the finished assembly. These are 43 pps and 166 pps - much better.
unitypackage
The smartest search
In the previous part, we made the search procedure smarter by implementing the A * algorithm . However, in reality we are still not performing the search in the most optimal way. In each iteration, we calculate the distances from the current cell to all its neighbors. This is true for cells that are not yet or are currently part of the search border. But the cells that have already been removed from the border, no longer need to be considered, because we have already found the shortest path to these cells. The correct implementation of A * skips these cells, so we can do the same.
Cell Search Phase
How do we know if a cell has already left the border? While we can not determine this. Therefore, you need to track in what phase of the search the cell is. She has not yet been in the border, or is in it now, or is abroad. We can track this by adding to a
HexCellsimple integer property. public int SearchPhase { get; set; }For example, 0 means that the cells have not yet reached, 1 - that the cell is in the border now, and 2 - that it has already been removed from the border.
Hitting the border
In
HexGrid.Searchwe can reset all cells to 0 and always use 1 for the border. Or we can increase the number of borders with each new search. Thanks to this, we will not have to deal with the dumping of cells if we each time increase the number of borders by two. int searchFrontierPhase;
…
void Search (HexCell fromCell, HexCell toCell, int speed) {
searchFrontierPhase += 2;
…
}Now we need to set the phase of the cell search when adding them to the border. The process begins with an initial cell, which is added to the border.
fromCell.SearchPhase = searchFrontierPhase;
fromCell.Distance = 0;
searchFrontier.Enqueue(fromCell);And also every time we add a neighbor to the border.
if (neighbor.Distance == int.MaxValue) {
neighbor.SearchPhase = searchFrontierPhase;
neighbor.Distance = distance;
neighbor.PathFrom = current;
neighbor.SearchHeuristic =
neighbor.coordinates.DistanceTo(toCell.coordinates);
searchFrontier.Enqueue(neighbor);
}Border check
Until now, to verify that the cell has not yet been added to the border, we used a distance equal to
int.MaxValue. Now we can compare the phase of the cell search with the current border.// if (neighbor.Distance == int.MaxValue) {
if (neighbor.SearchPhase < searchFrontierPhase) {
neighbor.SearchPhase = searchFrontierPhase;
neighbor.Distance = distance;
neighbor.PathFrom = current;
neighbor.SearchHeuristic =
neighbor.coordinates.DistanceTo(toCell.coordinates);
searchFrontier.Enqueue(neighbor);
}This means that we no longer need to reset cell distances before searching, that is, we will have to do less work, which is good.
for (int i = 0; i < cells.Length; i++) {
// cells[i].Distance = int.MaxValue;
cells[i].SetLabel(null);
cells[i].DisableHighlight();
}Leaving the border
When a cell is removed from the boundary, we denote this by an increase in its search phase. This puts her beyond the current border and before the next.
while (searchFrontier.Count > 0) {
HexCell current = searchFrontier.Dequeue();
current.SearchPhase += 1;
…
}Now we can skip cells removed from the border, avoiding pointless calculation and comparison of distances.
for (HexDirection d = HexDirection.NE; d <= HexDirection.NW; d++) {
HexCell neighbor = current.GetNeighbor(d);
if (
neighbor == null ||
neighbor.SearchPhase > searchFrontierPhase
) {
continue;
}
…
}At this point, our algorithm still produces the same results, but more efficiently. On my machine, the worst-case search takes 20 ms in the editor and 5 ms in the assembly.
We can also calculate how many times the cell has been processed by the algorithm, increasing the counter when calculating the distance to the cell. Previously, our algorithm in the worst case calculated 28,239 distances. In the ready-made A * algorithm, we calculate its 14,120 distances. The amount decreased by 50%. The degree of impact of these indicators on productivity depends on the costs in calculating the cost of moving. In our case, there is not much work here, so the improvement in the assembly is not very large, but it is very noticeable in the editor.
unitypackage
Clearing the way
When initiating a new search, we first need to clear the visualization of the previous path. While we do this, turn off the selection and remove the labels from each grid cell. This is a very difficult approach. Ideally, we need to discard only those cells that were part of the previous path.
Search Only
Let's start by completely removing the visualization code from
Search. He only needs to carry out a path search and does not have to know what we will do with this information. void Search (HexCell fromCell, HexCell toCell, int speed) {
searchFrontierPhase += 2;
if (searchFrontier == null) {
searchFrontier = new HexCellPriorityQueue();
}
else {
searchFrontier.Clear();
}
// for (int i = 0; i < cells.Length; i++) {
// cells[i].SetLabel(null);
// cells[i].DisableHighlight();
// }
// fromCell.EnableHighlight(Color.blue);
fromCell.SearchPhase = searchFrontierPhase;
fromCell.Distance = 0;
searchFrontier.Enqueue(fromCell);
while (searchFrontier.Count > 0) {
HexCell current = searchFrontier.Dequeue();
current.SearchPhase += 1;
if (current == toCell) {
// while (current != fromCell) {
// int turn = current.Distance / speed;
// current.SetLabel(turn.ToString());
// current.EnableHighlight(Color.white);
// current = current.PathFrom;
// }
// toCell.EnableHighlight(Color.red);
// break;
}
…
}
}To report that
Searchwe have found a way, we will return boolean. bool Search (HexCell fromCell, HexCell toCell, int speed) {
searchFrontierPhase += 2;
if (searchFrontier == null) {
searchFrontier = new HexCellPriorityQueue();
}
else {
searchFrontier.Clear();
}
fromCell.SearchPhase = searchFrontierPhase;
fromCell.Distance = 0;
searchFrontier.Enqueue(fromCell);
while (searchFrontier.Count > 0) {
HexCell current = searchFrontier.Dequeue();
current.SearchPhase += 1;
if (current == toCell) {
return true;
}
…
}
return false;
}Remember the way
When the path is found, we need to remember it. Thanks to this, we will be able to clean it in the future. Therefore, we will track the endpoints and whether there is a path between them.
HexCell currentPathFrom, currentPathTo;
bool currentPathExists;
…
public void FindPath (HexCell fromCell, HexCell toCell, int speed) {
System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
sw.Start();
currentPathFrom = fromCell;
currentPathTo = toCell;
currentPathExists = Search(fromCell, toCell, speed);
sw.Stop();
Debug.Log(sw.ElapsedMilliseconds);
}Display the path again
We can use the search data we recorded to visualize the path again. Let's create a new method for this
ShowPath. It will go through the cycle from the end to the beginning of the path, highlighting the cells and assigning a stroke value to their labels. To do this, we need to know the speed, so make it a parameter. If we don’t have a path, then the method simply selects the endpoints. void ShowPath (int speed) {
if (currentPathExists) {
HexCell current = currentPathTo;
while (current != currentPathFrom) {
int turn = current.Distance / speed;
current.SetLabel(turn.ToString());
current.EnableHighlight(Color.white);
current = current.PathFrom;
}
}
currentPathFrom.EnableHighlight(Color.blue);
currentPathTo.EnableHighlight(Color.red);
}Call this method in
FindPathafter the search. currentPathExists = Search(fromCell, toCell, speed);
ShowPath(speed);Sweep
We see the path again, but now it is not moving away. To clear it, create a method
ClearPath. In fact, it is a copy ShowPath, except that it disables the selection and labels, but does not include them. Having done this, he must clear the recorded path data that is no longer valid. void ClearPath () {
if (currentPathExists) {
HexCell current = currentPathTo;
while (current != currentPathFrom) {
current.SetLabel(null);
current.DisableHighlight();
current = current.PathFrom;
}
current.DisableHighlight();
currentPathExists = false;
}
currentPathFrom = currentPathTo = null;
}Using this method, we can clear the visualization of the old path by visiting only the necessary cells, the size of the map is no longer important. We will call it in
FindPathbefore starting a new search. sw.Start();
ClearPath();
currentPathFrom = fromCell;
currentPathTo = toCell;
currentPathExists = Search(fromCell, toCell, speed);
if (currentPathExists) {
ShowPath(speed);
}
sw.Stop();In addition, we will clear the path when creating a new map.
public bool CreateMap (int x, int z) {
…
ClearPath();
if (chunks != null) {
for (int i = 0; i < chunks.Length; i++) {
Destroy(chunks[i].gameObject);
}
}
…
}And also before loading another card.
public void Load (BinaryReader reader, int header) {
ClearPath();
…
}The path visualization is cleared again, as before this change. But now we are using a more efficient approach, and in the worst case of the search, the time has decreased to 14 milliseconds. Enough serious improvement only due to more intelligent cleaning. Assembly time decreased to 3 ms, which is 333 pps. Thanks to this, the search for paths is exactly applicable in real time.
Now that we have made a quick search for paths, we can remove the temporary debugging code.
public void FindPath (HexCell fromCell, HexCell toCell, int speed) {
// System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
// sw.Start();
ClearPath();
currentPathFrom = fromCell;
currentPathTo = toCell;
currentPathExists = Search(fromCell, toCell, speed);
ShowPath(speed);
// sw.Stop();
// Debug.Log(sw.ElapsedMilliseconds);
}unitypackage
Part 18: units
- We place the squads on the map.
- Save and load squads.
- We find ways for the troops.
- We move the units.
Now that we’ve figured out how to search for a path, let's place the squads on the map.
Reinforcements arrived
Creating squads
So far we have dealt only with cells and their fixed objects. Units differ from them in that they are mobile. A squad can mean anything of any scale, from one person or vehicle to an entire army. In this tutorial, we restrict ourselves to a simple generalized type of unit. After that, we will move on to supporting combinations of several types of units.
Prefab Squad
To work with squads, create a new type of component
HexUnit. For now, let's start with an empty one MonoBehaviour, and later add functionality to it.using UnityEngine;
public class HexUnit : MonoBehaviour {
}Create an empty game object with this component, which should become a prefab. This will be the root object of the squad.
Prefab squad.
Add a 3D model symbolizing the detachment as a child object. I used a simple scaled cube that I created blue material for. The root object determines the ground level of the detachment, therefore, we accordingly displace the child element.
Child cube element
Add a collider to the squad so that it is easier to select in the future. The collider of the standard cube is quite suitable for us, just make the collider fit in one cell.
Creating squad instances
Since we do not have gameplay yet, the creation of units takes place in the editing mode. Therefore, this should be addressed
HexMapEditor. To do this, he needs a prefab, so add a field HexUnit unitPrefaband connect it. public HexUnit unitPrefab;Connecting the prefab
When creating units, we will place them on the cell under the cursor. There
HandleInputis a code for finding this cell when editing a terrain. Now we also need it for the squads, so we will move the corresponding code to a separate method. HexCell GetCellUnderCursor () {
Ray inputRay = Camera.main.ScreenPointToRay(Input.mousePosition);
RaycastHit hit;
if (Physics.Raycast(inputRay, out hit)) {
return hexGrid.GetCell(hit.point);
}
return null;
}Now we can use this method in
HandleInputsimplifying it. void HandleInput () {
// Ray inputRay = Camera.main.ScreenPointToRay(Input.mousePosition);
// RaycastHit hit;
// if (Physics.Raycast(inputRay, out hit)) {
// HexCell currentCell = hexGrid.GetCell(hit.point);
HexCell currentCell = GetCellUnderCursor();
if (currentCell) {
…
}
else {
previousCell = null;
}
}Next, add a new method
CreateUnitthat also uses GetCellUnderCursor. If there is a cell, we will create a new squad. void CreateUnit () {
HexCell cell = GetCellUnderCursor();
if (cell) {
Instantiate(unitPrefab);
}
}To keep the hierarchy clean, let's use the grid as the parent for all the game objects in the squads.
void CreateUnit () {
HexCell cell = GetCellUnderCursor();
if (cell) {
HexUnit unit = Instantiate(unitPrefab);
unit.transform.SetParent(hexGrid.transform, false);
}
}The easiest way to add
HexMapEditorsupport for creating units is by pressing a key. Change the method Updateso that it calls CreateUnitwhen you press the U key. As with c HandleInput, this should happen if the cursor is not on top of the GUI element. First, we’ll check if we should edit the map, and if not, we’ll check whether we should add a squad. If so, then call CreateUnit. void Update () {
// if (
// Input.GetMouseButton(0) &&
// !EventSystem.current.IsPointerOverGameObject()
// ) {
// HandleInput();
// }
// else {
// previousCell = null;
// }
if (!EventSystem.current.IsPointerOverGameObject()) {
if (Input.GetMouseButton(0)) {
HandleInput();
return;
}
if (Input.GetKeyDown(KeyCode.U)) {
CreateUnit();
return;
}
}
previousCell = null;
}Created instance of squad
Troop Placement
Now we can create units, but they appear at the origin of the map. We need to put them in the right place. For this, it is necessary that the troops be aware of their position. Therefore, we add to the
HexUnitproperty Locationdenoting the cell they occupy. When setting the property, we will change the position of the squad so that it matches the position of the cell. public HexCell Location {
get {
return location;
}
set {
location = value;
transform.localPosition = value.Position;
}
}
HexCell location;Now I
HexMapEditor.CreateUnitmust assign the position of the squad cell under the cursor. Then the units will be where they should. void CreateUnit () {
HexCell cell = GetCellUnderCursor();
if (cell) {
HexUnit unit = Instantiate(unitPrefab);
unit.transform.SetParent(hexGrid.transform, false);
unit.Location = cell;
}
}Squads on the map
Unit Orientation
So far, all units have the same orientation, which looks rather unnatural. To revive them, add to the
HexUnitproperty Orientation. This is a float value that indicates the rotation of the squad along the Y axis in degrees. When setting it, we will accordingly change the rotation of the game object itself. public float Orientation {
get {
return orientation;
}
set {
orientation = value;
transform.localRotation = Quaternion.Euler(0f, value, 0f);
}
}
float orientation;In
HexMapEditor.CreateUnitassign a random rotation from 0 to 360 degrees. void CreateUnit () {
HexCell cell = GetCellUnderCursor();
if (cell) {
HexUnit unit = Instantiate(unitPrefab);
unit.transform.SetParent(hexGrid.transform, false);
unit.Location = cell;
unit.Orientation = Random.Range(0f, 360f);
}
}Different unit orientations
One squad per cell
Units look good if they are not created in one cell. In this case, we get a cluster of strange looking cubes.
Overlaid units
Some games allow the placement of several units in one place, others do not. Since it’s easier to work with one squad per cell, I will choose this option. This means that we should create a new squad only when the current cell is not occupied. So that you can find out, add to the
HexCellstandard property Unit. public HexUnit Unit { get; set; }We use this property in
HexUnit.Locationto let the cell know if the unit is on it. public HexCell Location {
get {
return location;
}
set {
location = value;
value.Unit = this;
transform.localPosition = value.Position;
}
}Now it
HexMapEditor.CreateUnitcan check if the current cell is free. void CreateUnit () {
HexCell cell = GetCellUnderCursor();
if (cell && !cell.Unit) {
HexUnit unit = Instantiate(unitPrefab);
unit.Location = cell;
unit.Orientation = Random.Range(0f, 360f);
}
}Editing Busy Cells
Initially, units are placed correctly, but everything can change if their cells are edited later. If the height of the cell changes, then the unit occupying it will either hang above it or plunge into it.
Hanging and drowned squads
The solution is to check the squad position after making changes. To do this, add the method to
HexUnit. So far, we are only interested in the position of the squad, so just ask it again. public void ValidateLocation () {
transform.localPosition = location.Position;
}We must coordinate the position of the detachment when updating the cell, what happens when the methods
Refreshor RefreshSelfOnlyobject are HexCellcalled. Of course, this is necessary only when there really is a detachment in the cell. void Refresh () {
if (chunk) {
chunk.Refresh();
…
if (Unit) {
Unit.ValidateLocation();
}
}
}
void RefreshSelfOnly () {
chunk.Refresh();
if (Unit) {
Unit.ValidateLocation();
}
}Removing squads
In addition to creating units, it would be useful to destroy them. Therefore, add to the
HexMapEditormethod DestroyUnit. He must check whether there is a detachment in the cell under the cursor, and if so, destroy the game object of the detachment. void DestroyUnit () {
HexCell cell = GetCellUnderCursor();
if (cell && cell.Unit) {
Destroy(cell.Unit.gameObject);
}
}Please note, to get to the squad, we go through the cell. To interact with the squad, just move the mouse over its cell. Therefore, for this to work, the squad does not have to have a collider. However, adding a collider makes it easier to select because it blocks the rays that would otherwise collide with the cell behind the squad.
Let's
Updateuse a combination of left Shift + U to destroy the squad . if (Input.GetKeyDown(KeyCode.U)) {
if (Input.GetKey(KeyCode.LeftShift)) {
DestroyUnit();
}
else {
CreateUnit();
}
return;
}In the case when we create and destroy several units, let's be careful and clear the property when removing the unit. That is, we explicitly clear the cell link to the squad. Add to the
HexUnitmethod Diethat deals with this, as well as the destruction of your own game object. public void Die () {
location.Unit = null;
Destroy(gameObject);
}We will call this method in
HexMapEditor.DestroyUnit, and not destroy the squad directly. void DestroyUnit () {
HexCell cell = GetCellUnderCursor();
if (cell && cell.Unit) {
// Destroy(cell.Unit.gameObject);
cell.Unit.Die();
}
}unitypackage
Saving and loading squads
Now that we can have units on the map, we must include them in the saving and loading process. We can approach this task in two ways. The first is to record squad data when recording a cell so that the cell and squad data are mixed. The second way is to save cell and squad data separately. Although it may seem that the first approach is easier to implement, the second gives us more structured data. If we share the data, then it will be easier to work with them in the future.
Unit Tracking
To keep all units together, we need to track them. We will do this by adding to the
HexGridlist of units. This list should contain all units on the map. List units = new List(); When creating or loading a new map, we need to get rid of all the units on the map. To simplify this process, create a method
ClearUnitsthat kills everyone on the list and clears it. void ClearUnits () {
for (int i = 0; i < units.Count; i++) {
units[i].Die();
}
units.Clear();
}We call this method in
CreateMapand in Load. Let's do it after cleaning the way. public bool CreateMap (int x, int z) {
…
ClearPath();
ClearUnits();
…
}
…
public void Load (BinaryReader reader, int header) {
ClearPath();
ClearUnits();
…
}Adding squads to the grid
Now, when creating new units, we need to add them to the list. Let's set a method for this
AddUnit, which will also deal with the location of the squad and the parameters of its parent object. public void AddUnit (HexUnit unit, HexCell location, float orientation) {
units.Add(unit);
unit.transform.SetParent(transform, false);
unit.Location = location;
unit.Orientation = orientation;
}Now it
HexMapEditor.CreatUnitwill be enough to call AddUnitwith a new instance of the detachment, its location and random orientation. void CreateUnit () {
HexCell cell = GetCellUnderCursor();
if (cell && !cell.Unit) {
// HexUnit unit = Instantiate(unitPrefab);
// unit.transform.SetParent(hexGrid.transform, false);
// unit.Location = cell;
// unit.Orientation = Random.Range(0f, 360f);
hexGrid.AddUnit(
Instantiate(unitPrefab), cell, Random.Range(0f, 360f)
);
}
}Removing squads from the grid
Add a method to remove squad and c
HexGrid. Just remove the squad from the list and order it to die. public void RemoveUnit (HexUnit unit) {
units.Remove(unit);
unit.Die();
}We call this method in
HexMapEditor.DestroyUnit, instead of destroying the squad directly. void DestroyUnit () {
HexCell cell = GetCellUnderCursor();
if (cell && cell.Unit) {
// cell.Unit.Die();
hexGrid.RemoveUnit(cell.Unit);
}
}Saving units
Since we are going to keep all the units together, we need to remember which cells they occupy. The most reliable way is to save the coordinates of their location. To make this possible, we add the fields X and Z to the
HexCoordinatesmethod Savethat writes it.using UnityEngine;
using System.IO;
[System.Serializable]
public struct HexCoordinates {
…
public void Save (BinaryWriter writer) {
writer.Write(x);
writer.Write(z);
}
}The method
Savefor HexUnitcan now record the coordinates and orientation of the squad. This is all the data of the units that we have at the moment.using UnityEngine;
using System.IO;
public class HexUnit : MonoBehaviour {
…
public void Save (BinaryWriter writer) {
location.coordinates.Save(writer);
writer.Write(orientation);
}
}Since it
HexGridtracks units, its method Savewill record the data of units. First, write down the total number of units, and then go around them all in a loop. public void Save (BinaryWriter writer) {
writer.Write(cellCountX);
writer.Write(cellCountZ);
for (int i = 0; i < cells.Length; i++) {
cells[i].Save(writer);
}
writer.Write(units.Count);
for (int i = 0; i < units.Count; i++) {
units[i].Save(writer);
}
}We changed the stored data, so we will increase the version number
SaveLoadMenu.Saveto 2. The old boot code will still work, because it simply won’t read the squad data. However, you need to increase the version number to indicate that there is unit information in the file. void Save (string path) {
using (
BinaryWriter writer =
new BinaryWriter(File.Open(path, FileMode.Create))
) {
writer.Write(2);
hexGrid.Save(writer);
}
}Loading squads
Since it
HexCoordinatesis a structure, it does not make much sense to add the usual method to it Load. Let's make it a static method that reads and returns stored coordinates. public static HexCoordinates Load (BinaryReader reader) {
HexCoordinates c;
c.x = reader.ReadInt32();
c.z = reader.ReadInt32();
return c;
}Since the number of units is variable, we do not have pre-existing units into which data can be loaded. We can create new instances of units before loading their data, but this will require that we
HexGridcreate instances of new units at boot time. So it’s better to leave it HexUnit. We also use the static method HexUnit.Load. Let's start by simply reading these squads. To read the value of the orientation float, we use the method BinaryReader.ReadSingle.Why single?
A type
floatis a single-precision floating-point number that is four bytes long. There are also double precision numbers, specified as double, which are eight bytes long. In Unity, they are rarely used. public static void Load (BinaryReader reader) {
HexCoordinates coordinates = HexCoordinates.Load(reader);
float orientation = reader.ReadSingle();
}The next step is to create an instance of a new squad. However, for this we need a link to the unit’s prefab. In order not to complicate it yet, let's add a
HexUnitstatic method for this . public static HexUnit unitPrefab;To set this link, let's use it again
HexGrid, as we did with the noise texture. When we need to support many types of units, we will move on to a better solution. public HexUnit unitPrefab;
…
void Awake () {
HexMetrics.noiseSource = noiseSource;
HexMetrics.InitializeHashGrid(seed);
HexUnit.unitPrefab = unitPrefab;
CreateMap(cellCountX, cellCountZ);
}
…
void OnEnable () {
if (!HexMetrics.noiseSource) {
HexMetrics.noiseSource = noiseSource;
HexMetrics.InitializeHashGrid(seed);
HexUnit.unitPrefab = unitPrefab;
}
}We pass the unit’s prefab.
After connecting the field, we no longer need a direct link to
HexMapEditor. Instead, he can use HexUnit.unitPrefab.// public HexUnit unitPrefab;
…
void CreateUnit () {
HexCell cell = GetCellUnderCursor();
if (cell && !cell.Unit) {
hexGrid.AddUnit(
Instantiate(HexUnit.unitPrefab), cell, Random.Range(0f, 360f)
);
}
}Now we can create an instance of the new squad in
HexUnit.Load. Instead of returning it, we can use the loaded coordinates and orientation to add it to the grid. To make this possible, add a parameter HexGrid. public static void Load (BinaryReader reader, HexGrid grid) {
HexCoordinates coordinates = HexCoordinates.Load(reader);
float orientation = reader.ReadSingle();
grid.AddUnit(
Instantiate(unitPrefab), grid.GetCell(coordinates), orientation
);
}In the end,
HexGrid.Loadwe count the number of units and use it to load all stored units, passing ourselves as an additional argument. public void Load (BinaryReader reader, int header) {
…
int unitCount = reader.ReadInt32();
for (int i = 0; i < unitCount; i++) {
HexUnit.Load(reader, this);
}
}Of course, this will work only for save files with version no lower than 2, in younger versions there are no units to load.
if (header >= 2) {
int unitCount = reader.ReadInt32();
for (int i = 0; i < unitCount; i++) {
HexUnit.Load(reader, this);
}
}Now we can correctly upload version 2 files, so in
SaveLoadMenu.Loadincrease the number of the supported version to 2. void Load (string path) {
if (!File.Exists(path)) {
Debug.LogError("File does not exist " + path);
return;
}
using (BinaryReader reader = new BinaryReader(File.OpenRead(path))) {
int header = reader.ReadInt32();
if (header <= 2) {
hexGrid.Load(reader, header);
HexMapCamera.ValidatePosition();
}
else {
Debug.LogWarning("Unknown map format " + header);
}
}
}unitypackage
Troop Movement
Squads are mobile, so we must be able to move them around the map. We already have a path search code, but so far we have tested it only for arbitrary places. Now we need to remove the old test UI and create a new UI for squad management.
Map Editor Cleanup
Moving units along paths is part of the gameplay, it does not apply to the map editor. Therefore, we will get rid
HexMapEditorof all the code associated with finding the path.// HexCell previousCell, searchFromCell, searchToCell;
HexCell previousCell;
…
void HandleInput () {
HexCell currentCell = GetCellUnderCursor();
if (currentCell) {
if (previousCell && previousCell != currentCell) {
ValidateDrag(currentCell);
}
else {
isDrag = false;
}
if (editMode) {
EditCells(currentCell);
}
// else if (
// Input.GetKey(KeyCode.LeftShift) && searchToCell != currentCell
// ) {
// if (searchFromCell != currentCell) {
// if (searchFromCell) {
// searchFromCell.DisableHighlight();
// }
// searchFromCell = currentCell;
// searchFromCell.EnableHighlight(Color.blue);
// if (searchToCell) {
// hexGrid.FindPath(searchFromCell, searchToCell, 24);
// }
// }
// }
// else if (searchFromCell && searchFromCell != currentCell) {
// if (searchToCell != currentCell) {
// searchToCell = currentCell;
// hexGrid.FindPath(searchFromCell, searchToCell, 24);
// }
// }
previousCell = currentCell;
}
else {
previousCell = null;
}
}After removing this code, it no longer makes sense to leave the editor active when we are not in edit mode. Therefore, instead of a mode tracking field, we can simply enable or disable the component
HexMapEditor. In addition, the editor now does not have to deal with UI labels.// bool editMode;
…
public void SetEditMode (bool toggle) {
// editMode = toggle;
// hexGrid.ShowUI(!toggle);
enabled = toggle;
}
…
void HandleInput () {
HexCell currentCell = GetCellUnderCursor();
if (currentCell) {
if (previousCell && previousCell != currentCell) {
ValidateDrag(currentCell);
}
else {
isDrag = false;
}
// if (editMode) {
EditCells(currentCell);
// }
previousCell = currentCell;
}
else {
previousCell = null;
}
}Since by default we are not in map editing mode, in Awake we will disable the editor.
void Awake () {
terrainMaterial.DisableKeyword("GRID_ON");
SetEditMode(false);
}Use raycast to search for the current cell under the cursor is necessary when editing the map, and to manage units. Perhaps in the future it will be useful to us for something else. Let's move the raycasting logic from
HexGridto a new method GetCellwith a beam parameter. public HexCell GetCell (Ray ray) {
RaycastHit hit;
if (Physics.Raycast(ray, out hit)) {
return GetCell(hit.point);
}
return null;
}HexMapEditor.GetCellUniderCursor may just call this method with the cursor beam. HexCell GetCellUnderCursor () {
return
hexGrid.GetCell(Camera.main.ScreenPointToRay(Input.mousePosition));
}Game UI
To control the game mode UI, we will use a new component. While he will only deal with the selection and movement of units. Create a new component type for it
HexGameUI. To do his job, a link to the grid is enough for him.using UnityEngine;
using UnityEngine.EventSystems;
public class HexGameUI : MonoBehaviour {
public HexGrid grid;
}Add this component to the new game object in the UI hierarchy. He does not have to have his own object, but it will be obvious to us that there is a separate UI for the game.
Game UI Object
Add a
HexGameUImethod SetEditMode, as in HexMapEditor. The game UI should be turned on when we are not in edit mode. Also, labels need to be included here because the game UI works with paths. public void SetEditMode (bool toggle) {
enabled = !toggle;
grid.ShowUI(!toggle);
}Add the game UI method with the event list of the edit mode switch. This will mean that when the player changes the mode, both methods are called.
Several event methods.
Track current cell
Depending on the situation,
HexGameUIyou need to know which cell is currently under the cursor. Therefore, we add a field to it currentCell. HexCell currentCell;Create a method
UpdateCurrentCellthat uses the HexGrid.GetCellcursor beam to update this field. void UpdateCurrentCell () {
currentCell =
grid.GetCell(Camera.main.ScreenPointToRay(Input.mousePosition));
}When updating the current cell, we may need to find out if it has changed. Force to
UpdateCurrentCellreturn this information. bool UpdateCurrentCell () {
HexCell cell =
grid.GetCell(Camera.main.ScreenPointToRay(Input.mousePosition));
if (cell != currentCell) {
currentCell = cell;
return true;
}
return false;
}Unit Selection
Before moving a squad, it must be selected and tracked. Therefore, add a field
selectedUnit. HexUnit selectedUnit;When we try to make a selection, we need to start by updating the current cell. If the current cell is then the unit occupying this cell becomes the selected unit. If there is no unit in the cell, then no unit is selected. Let's create a method for this
DoSelection. void DoSelection () {
UpdateCurrentCell();
if (currentCell) {
selectedUnit = currentCell.Unit;
}
}We realize the choice of units with a simple click of the mouse. Therefore, we add a method
Updatethat makes a selection when the mouse button is activated. Of course, we need to execute it only when the cursor is not above the GUI element. void Update () {
if (!EventSystem.current.IsPointerOverGameObject()) {
if (Input.GetMouseButtonDown(0)) {
DoSelection();
}
}
}At this stage, we learned how to select one unit at a time with the click of a mouse. When you click on an empty cell, the selection of any unit is removed. But while we do not receive any visual confirmation of this.
Squad search
When a unit is selected, we can use its location as a starting point for finding a path. To activate this, we will not require another click of the mouse button. Instead, we will automatically find and show the path between the squad position and the current cell. We will always do this in
Update, except when the choice is made. To do this, when we have a detachment, we call the method DoPathfinding. void Update () {
if (!EventSystem.current.IsPointerOverGameObject()) {
if (Input.GetMouseButtonDown(0)) {
DoSelection();
}
else if (selectedUnit) {
DoPathfinding();
}
}
}DoPathfindingjust updates the current cell and calls HexGrid.FindPathif there is an endpoint. We again use a constant speed of 24. void DoPathfinding () {
UpdateCurrentCell();
grid.FindPath(selectedUnit.Location, currentCell, 24);
}Please note that we should not find a new path every time we update, but only when the current cell changes.
void DoPathfinding () {
if (UpdateCurrentCell()) {
grid.FindPath(selectedUnit.Location, currentCell, 24);
}
}Finding a path for a squad
Now we see the paths that appear when you move the cursor after selecting a squad. Thanks to this, it is obvious which unit is selected. However, the paths are not always cleared correctly. First, let's clear the old path if the cursor is outside the map.
void DoPathfinding () {
if (UpdateCurrentCell()) {
if (currentCell) {
grid.FindPath(selectedUnit.Location, currentCell, 24);
}
else {
grid.ClearPath();
}
}
}Of course, this requires that it
HexGrid.ClearPathbe common, so we make such a change. public void ClearPath () {
…
}Secondly, we will clear the old path when choosing a detachment.
void DoSelection () {
grid.ClearPath();
UpdateCurrentCell();
if (currentCell) {
selectedUnit = currentCell.Unit;
}
}Finally, we will clear the path when changing the editing mode.
public void SetEditMode (bool toggle) {
enabled = !toggle;
grid.ShowUI(!toggle);
grid.ClearPath();
}Search for valid endpoints only
We cannot always find the way, because sometimes it is impossible to reach the final cell. This is normal. But sometimes the final cell itself is unacceptable. For example, we decided that paths cannot include underwater cells. But it may depend on the unit. Let's add to a
HexUnitmethod that tells us whether a cell is a valid endpoint. Underwater cells are not. public bool IsValidDestination (HexCell cell) {
return !cell.IsUnderwater;
}In addition, we allowed only one unit to stand in the cell. Therefore, the final cell will not be valid if it is busy.
public bool IsValidDestination (HexCell cell) {
return !cell.IsUnderwater && !cell.Unit;
}We use this method in
HexGameUI.DoPathfindingto ignore invalid endpoints. void DoPathfinding () {
if (UpdateCurrentCell()) {
if (currentCell && selectedUnit.IsValidDestination(currentCell)) {
grid.FindPath(selectedUnit.Location, currentCell, 24);
}
else {
grid.ClearPath();
}
}
}Move to end point
If we have a valid path, then we are able to move the squad to the end point.
HexGridknows when this can be done. We make it pass this information in a new read-only property HasPath. public bool HasPath {
get {
return currentPathExists;
}
}To move a squad, add to the
HexGameUImethod DoMove. This method will be called when a command is issued and if a unit is selected. Therefore, he must check if there is a way, and if so, change the location of the detachment. While we immediately teleport the squad to the end point. In one of the following tutorials, we will make the squad actually go all the way. void DoMove () {
if (grid.HasPath) {
selectedUnit.Location = currentCell;
grid.ClearPath();
}
}Let's use the mouse button 1 (right click) to submit the command. We will check this if a detachment is selected. If the button is not pressed, then we search for the path.
void Update () {
if (!EventSystem.current.IsPointerOverGameObject()) {
if (Input.GetMouseButtonDown(0)) {
DoSelection();
}
else if (selectedUnit) {
if (Input.GetMouseButtonDown(1)) {
DoMove();
}
else {
DoPathfinding();
}
}
}
}Now we can move units! But sometimes they refuse to find a way to some cells. In particular, to those cells in which the detachment used to be. This happens because it
HexUnitdoes not update the old location when setting a new one. To fix this, we will clear the link to the squad in its old location. public HexCell Location {
get {
return location;
}
set {
if (location) {
location.Unit = null;
}
location = value;
value.Unit = this;
transform.localPosition = value.Position;
}
}Avoid squads
Finding the way now works correctly, and units can teleport on the map. Although they cannot move to cells that already have a squad, detachments standing in the way are ignored.
Units on the way are ignored.
Units of the same faction can usually move through each other, but so far we have no factions. Therefore, let's consider all the units as disconnected from each other and blocking the paths. This can be implemented by skipping busy cells in
HexGrid.Search. if (
neighbor == null ||
neighbor.SearchPhase > searchFrontierPhase
) {
continue;
}
if (neighbor.IsUnderwater || neighbor.Unit) {
continue;
}Avoid detachments
unitypackage
Part 19: Motion Animation
- We move the units between the cells.
- Visualize the path traveled.
- We move the troops along the curves.
- We force the troops to look in the direction of movement.
In this part, we will force units instead of teleportation to move along the tracks.
Squads on the way
Movement along the way
In the previous part, we added units and the ability to move them. Although we used the search for the path to determine the valid endpoints, after giving the command, the troops simply teleported to the final cell. To actually follow the found path, we need to track this path and create an animation process that forces the squad to move from cell to cell. Since looking at the animations it is difficult to notice how the squad moved, we also visualize the path traveled with the help of gizmos. But before we move on, we need to fix the error.
Error with turns
Due to an oversight, we incorrectly calculate the course at which the cell will be reached. Now we determine the course by dividing the total distance by the squad speed
, and discarding the remainder. The error occurs when to get into the cell you need to spend exactly all the remaining movement points per move. For example, when each step costs 1, and the speed is 3, then we can move three cells per turn. However, with existing calculations, we can only take two steps in the first move, because for the third step
.The summed costs of moving with incorrectly defined moves, speed 3
For the correct calculation of moves we need to move the border one step from the initial cell. We can do this by reducing the distance by 1 before calculating the move. Then the move for the third step will be
Correct moves
We can do this by changing the calculation formula to
. We’ll make this change to HexGrid.Search. bool Search (HexCell fromCell, HexCell toCell, int speed) {
…
while (searchFrontier.Count > 0) {
…
int currentTurn = (current.Distance - 1) / speed;
for (HexDirection d = HexDirection.NE; d <= HexDirection.NW; d++) {
…
int distance = current.Distance + moveCost;
int turn = (distance - 1) / speed;
if (turn > currentTurn) {
distance = turn * speed + moveCost;
}
…
}
}
return false;
}We also change the marks of the moves.
void ShowPath (int speed) {
if (currentPathExists) {
HexCell current = currentPathTo;
while (current != currentPathFrom) {
int turn = (current.Distance - 1) / speed;
…
}
}
…
}Note that with this approach, the initial cell path is −1. This is normal, because we do not display it, and the search algorithm remains operational.
Getting way
Moving along the path is the task of the squad. In order for him to do this, he needs to know the way. We have this information
HexGrid, so let's add a method to it to get the current path in the form of a list of cells. He can take it from the pool of lists and return if there really is a path. public List GetPath () {
if (!currentPathExists) {
return null;
}
List path = ListPool.Get();
return path;
} The list is filled by following the link path from the final cell to the initial one, as is done when visualizing the path.
List path = ListPool.Get();
for (HexCell c = currentPathTo; c != currentPathFrom; c = c.PathFrom) {
path.Add(c);
}
return path; In this case, we need the whole path, which includes the initial cell.
for (HexCell c = currentPathTo; c != currentPathFrom; c = c.PathFrom) {
path.Add(c);
}
path.Add(currentPathFrom);
return path;Now we have the path in the reverse order. We can work with him, but it will not be very intuitive. Let's flip the list so that it goes from beginning to end.
path.Add(currentPathFrom);
path.Reverse();
return path;Motion request
Now we can add to the
HexUnitmethod, ordering him to follow the path. Initially, we simply let him teleport to the final cell. We will not immediately return the list to the pool, because it will be useful to us for a while.using UnityEngine;
using System.Collections.Generic;
using System.IO;
public class HexUnit : MonoBehaviour {
…
public void Travel (List path) {
Location = path[path.Count - 1];
}
…
} To request movement, we change it
HexGameUI.DoMoveso that it calls a new method with the current path, and not just sets the location of the unit. void DoMove () {
if (grid.HasPath) {
// selectedUnit.Location = currentCell;
selectedUnit.Travel(grid.GetPath());
grid.ClearPath();
}
}Path visualization
Before we start animating the squad, let's check that the paths are correct. We will do this by ordering to
HexUnitremember the path along which it must move, so that it can be visualized using gizmos. List pathToTravel;
…
public void Travel (List path) {
Location = path[path.Count - 1];
pathToTravel = path;
} Add a method
OnDrawGizmosto show the last path to go (if it exists). If the unit has not yet moved, the path should be equal null. But due to the serialization of Unity during editing after recompilation in Play mode, it can also be an empty list. void OnDrawGizmos () {
if (pathToTravel == null || pathToTravel.Count == 0) {
return;
}
}The easiest way to show the path is to draw a gizmo sphere for each cell of the path. A sphere with a radius of 2 units is suitable for us.
void OnDrawGizmos () {
if (pathToTravel == null || pathToTravel.Count == 0) {
return;
}
for (int i = 0; i < pathToTravel.Count; i++) {
Gizmos.DrawSphere(pathToTravel[i].Position, 2f);
}
}Since we will show the paths for the detachment, we will be able to simultaneously see all of its last paths.
Gizmos display the last paths traveled.
In order to better show the cell connections, we draw several spheres in a loop on a line between the previous and current cells. To do this, we need to start the process from the second cell. Spheres can be arranged using linear interpolation with an increment of 0.1 units, so that we get ten spheres per segment.
for (int i = 1; i < pathToTravel.Count; i++) {
Vector3 a = pathToTravel[i - 1].Position;
Vector3 b = pathToTravel[i].Position;
for (float t = 0f; t < 1f; t += 0.1f) {
Gizmos.DrawSphere(Vector3.Lerp(a, b, t), 2f);
}
}More obvious ways
Glide along the way
You can use the same method to move units. Let's create a coroutine for this. Instead of drawing a gizmo, we will set the position of the squad. Instead of incrementing, we will use 0.1 time delta, and we will perform yield for each iteration. In this case, the squad will move from one cell to the next in one second.
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using System.IO;
public class HexUnit : MonoBehaviour {
…
IEnumerator TravelPath () {
for (int i = 1; i < pathToTravel.Count; i++) {
Vector3 a = pathToTravel[i - 1].Position;
Vector3 b = pathToTravel[i].Position;
for (float t = 0f; t < 1f; t += Time.deltaTime) {
transform.localPosition = Vector3.Lerp(a, b, t);
yield return null;
}
}
}
…
}Let's start coroutine at the end of the method
Travel. But first, we will stop all existing coroutines. So we guarantee that two coroutines will not start at the same time, otherwise this would lead to very strange results. public void Travel (List path) {
Location = path[path.Count - 1];
pathToTravel = path;
StopAllCoroutines();
StartCoroutine(TravelPath());
} Moving one cell per second is pretty slow. The player during the game will not want to wait so long. You can make the squad move speed a configuration option, but for now, let's use a constant. I assigned her a value of 4 cells per second; it's pretty fast, but lets notice what is happening.
const float travelSpeed = 4f;
…
IEnumerator TravelPath () {
for (int i = 1; i < pathToTravel.Count; i++) {
Vector3 a = pathToTravel[i - 1].Position;
Vector3 b = pathToTravel[i].Position;
for (float t = 0f; t < 1f; t += Time.deltaTime * travelSpeed) {
transform.localPosition = Vector3.Lerp(a, b, t);
yield return null;
}
}
}Just as we can visualize several paths simultaneously, we can make several units travel at the same time. From the point of view of the game state, the movement is still teleportation, the animations are exclusively visual. Units instantly occupy the final cell. You can even find ways and start a new move before they arrive. In this case, they are visually teleported to the beginning of a new path. This can be avoided by blocking units or even the entire UI while they are moving, but such a quick reaction is quite convenient when developing and testing movements.
Moving units.
What about the difference in height?
Так как мы выполняем интерполяцию между позициями ячеек, мы интерполируем и вертикальную позицию отряда. Так как это не соответствует настоящей геометрии, при движении отряд может висеть над рельефом или утопать в нём. Так как анимация быстра и обычно наблюдается издалека, это не очень заметно. Игроки заняты игрой, а не рассматриванием движения отдельных отрядов. Если проанализировать игры с изменяемой высотой, например Endless Legend, то можно заметить, что отряды нам тоже висят или утопают в рельефе. Если это устраивает разработчиков игры, то нас и подавно.
Позиция после компиляции
One of the drawbacks of corutin is that they do not “survive” when recompiled in Play mode. Although the game state is always true, this can lead to squads getting stuck somewhere in their last path if recompilation is started while they are still moving. To mitigate the consequences, let's make sure that, after recompilation, the units are always in the correct position. This can be done by updating their position in
OnEnable. void OnEnable () {
if (location) {
transform.localPosition = location.Position;
}
}unitypackage
Smooth movement
The movement from the center to the center of the cell looks too mechanistic and creates sharp changes in direction. For many games, this will be normal, but unacceptable if you need at least a slightly realistic movement. So let's change the movement to make it look a little more organic.
Moving from rib to rib
The squad begins its journey from the center of the cell. It passes to the middle of the cell edge, and then enters the next cell. Instead of moving toward the center, he can head straight for the next edge that he must cross. In fact, the unit will cut the path when it needs to change direction. This is possible for all cells except the end points of the path.
Three ways to move from edge to edge
Let's adapt
OnDrawGizmosto displaying the paths generated in this way. It must interpolate between the edges of the cells, which can be found by averaging the positions of neighboring cells. It is enough for us to calculate one edge per iteration, reusing the value from the previous iteration. Thus, we can make the method work for the initial cell, but instead of the edge we take its position. void OnDrawGizmos () {
if (pathToTravel == null || pathToTravel.Count == 0) {
return;
}
Vector3 a, b = pathToTravel[0].Position;
for (int i = 1; i < pathToTravel.Count; i++) {
// Vector3 a = pathToTravel[i - 1].Position;
// Vector3 b = pathToTravel[i].Position;
a = b;
b = (pathToTravel[i - 1].Position + pathToTravel[i].Position) * 0.5f;
for (float t = 0f; t < 1f; t += 0.1f) {
Gizmos.DrawSphere(Vector3.Lerp(a, b, t), 2f);
}
}
}To reach the center of the end cell, we need to use the cell position as the last point, not the edge. You can add verification of this case to the loop, but it is such a simple code that it will be more obvious to simply duplicate the code and slightly change it.
void OnDrawGizmos () {
…
for (int i = 1; i < pathToTravel.Count; i++) {
…
}
a = b;
b = pathToTravel[pathToTravel.Count - 1].Position;
for (float t = 0f; t < 1f; t += 0.1f) {
Gizmos.DrawSphere(Vector3.Lerp(a, b, t), 2f);
}
}Rib-based
paths The resulting paths are less like zigzags, and the maximum turning angle is reduced from 120 ° to 90 °. This can be considered an improvement, so we apply the same changes in coroutine
TravelPathto see how it looks in the animation. IEnumerator TravelPath () {
Vector3 a, b = pathToTravel[0].Position;
for (int i = 1; i < pathToTravel.Count; i++) {
// Vector3 a = pathToTravel[i - 1].Position;
// Vector3 b = pathToTravel[i].Position;
a = b;
b = (pathToTravel[i - 1].Position + pathToTravel[i].Position) * 0.5f;
for (float t = 0f; t < 1f; t += Time.deltaTime * travelSpeed) {
transform.localPosition = Vector3.Lerp(a, b, t);
yield return null;
}
}
a = b;
b = pathToTravel[pathToTravel.Count - 1].Position;
for (float t = 0f; t < 1f; t += Time.deltaTime * travelSpeed) {
transform.localPosition = Vector3.Lerp(a, b, t);
yield return null;
}
}Moving with a changing speed
After cutting the angles, the length of the path segments became dependent on the change in direction. But we set the speed in cells per second. As a result, the detachment speed changes randomly.
Following curves
Instantaneous changes in direction and speed when crossing cell boundaries look ugly. Better use a gradual change of direction. We can add support for this by forcing troops to follow along curves rather than straight lines. You can use Bezier curves for this. In particular, we can take quadratic Bezier curves at which the center of the cells will be the middle control points. In this case, the tangents of adjacent curves will be mirror images of each other, that is, the entire path will turn into a continuous smooth curve.
Curves from edge to edge
Create an auxiliary class
Bezierwith a method for obtaining points on a quadratic Bezier curve. As explained in the Curves and Splines tutorial , the formula is used for thiswhere , and Are the control points, and t is the interpolator.using UnityEngine;
public static class Bezier {
public static Vector3 GetPoint (Vector3 a, Vector3 b, Vector3 c, float t) {
float r = 1f - t;
return r * r * a + 2f * r * t * b + t * t * c;
}
}Shouldn't GetPoint be limited to 0-1?
Since we use interpolators only in the interval 0-1, we do not need to limit them. In practice, when interpolating along curves, this happens almost always. If you want, you can create a version
GetPointClampedthat contains the parameter t. Or make it the default behavior, and call the above method GetPointUnclamped.To show the curve path in
OnDrawGizmos, we need to track not two, but three points. An additional point is the center of the cell with which we are working at the current iteration, which has an index i - 1, because the cycle begins with 1. Having received all the points, we can replace it Vector3.Lerpwith Bezier.GetPoint. In the start and end cells, instead of the end and midpoints, we can simply use the center of the cell.
void OnDrawGizmos () {
if (pathToTravel == null || pathToTravel.Count == 0) {
return;
}
Vector3 a, b, c = pathToTravel[0].Position;
for (int i = 1; i < pathToTravel.Count; i++) {
a = c;
b = pathToTravel[i - 1].Position;
c = (b + pathToTravel[i].Position) * 0.5f;
for (float t = 0f; t < 1f; t += Time.deltaTime * travelSpeed) {
Gizmos.DrawSphere(Bezier.GetPoint(a, b, c, t), 2f);
}
}
a = c;
b = pathToTravel[pathToTravel.Count - 1].Position;
c = b;
for (float t = 0f; t < 1f; t += 0.1f) {
Gizmos.DrawSphere(Bezier.GetPoint(a, b, c, t), 2f);
}
}Paths created using Bezier curves A curved
path looks much better. We apply the same changes to
TravelPathand see how the units are animated with this approach. IEnumerator TravelPath () {
Vector3 a, b, c = pathToTravel[0].Position;
for (int i = 1; i < pathToTravel.Count; i++) {
a = c;
b = pathToTravel[i - 1].Position;
c = (b + pathToTravel[i].Position) * 0.5f;
for (float t = 0f; t < 1f; t += Time.deltaTime * travelSpeed) {
transform.localPosition = Bezier.GetPoint(a, b, c, t);
yield return null;
}
}
a = c;
b = pathToTravel[pathToTravel.Count - 1].Position;
c = b;
for (float t = 0f; t < 1f; t += Time.deltaTime * travelSpeed) {
transform.localPosition = Bezier.GetPoint(a, b, c, t);
yield return null;
}
}We move along the curves. The
animation also became smooth, even when the speed of the detachment is unstable. Since the tangents of the curve of the adjacent segments coincide, the speed is continuous. The change in speed occurs gradually and happens when a detachment passes through the cell, slowing down when changing direction. If he goes straight, then the speed remains constant. In addition, the squad begins and ends its journey at zero speed. This mimics the natural movement, so leave it like that.
Time tracking
Up to this point, we started iterating over each of the segments from 0, continuing until we reach 1. This works fine when increasing by a constant value, but our iteration depends on the time delta. When the iteration over one segment is completed, we are likely to exceed 1 by some amount, depending on the delta of time. This is invisible at high frame rates, but can lead to jerks at low frame rates.
To avoid time loss, we need to transfer the remaining time from one segment to the next. This can be done by tracking
talong the entire path, and not just in each segment. Then at the end of each segment we will subtract 1 from it. IEnumerator TravelPath () {
Vector3 a, b, c = pathToTravel[0].Position;
float t = 0f;
for (int i = 1; i < pathToTravel.Count; i++) {
a = c;
b = pathToTravel[i - 1].Position;
c = (b + pathToTravel[i].Position) * 0.5f;
for (; t < 1f; t += Time.deltaTime * travelSpeed) {
transform.localPosition = Bezier.GetPoint(a, b, c, t);
yield return null;
}
t -= 1f;
}
a = c;
b = pathToTravel[pathToTravel.Count - 1].Position;
c = b;
for (; t < 1f; t += Time.deltaTime * traveSpeed) {
transform.localPosition = Bezier.GetPoint(a, b, c, t);
yield return null;
}
}If we are already doing this, let's make sure that the time delta is taken into account at the beginning of the path. This means that we will begin to move immediately, and will not stand idle for one frame.
float t = Time.deltaTime * travelSpeed;In addition, we do not finish exactly at the point in time when the path should end, but moments before. Here, the difference may also depend on the frame rate. Therefore, let's make the squad complete the path exactly at the end point.
IEnumerator TravelPath () {
…
transform.localPosition = location.Position;
}unitypackage
Orientation animation
The units began to move along a smooth curve, but they did not change orientation in accordance with the direction of movement. As a result, they seem to glide. To make the movement look like a real movement, we need to rotate them.
Looking forward
As in the Curves and Splines tutorial , we can use the derivative of the curve to determine the orientation of the unit. The formula for the derivative of a quadratic Bezier curve:
. Add to the Beziermethod to calculate it. public static Vector3 GetDerivative (
Vector3 a, Vector3 b, Vector3 c, float t
) {
return 2f * ((1f - t) * (b - a) + t * (c - b));
}The derivative vector is located on one straight line with the direction of motion. We can use the method
Quaternion.LookRotationto convert it into a squad turn. We will carry it out at every step in HexUnit.TravelPath. transform.localPosition = Bezier.GetPoint(a, b, c, t);
Vector3 d = Bezier.GetDerivative(a, b, c, t);
transform.localRotation = Quaternion.LookRotation(d);
yield return null;
…
transform.localPosition = Bezier.GetPoint(a, b, c, t);
Vector3 d = Bezier.GetDerivative(a, b, c, t);
transform.localRotation = Quaternion.LookRotation(d);
yield return null;Is there no mistake at the beginning of the path?
The path begins with a curve going from the center of the initial cell to its edge. We made points and equal to the curve, so we get a beautiful acceleration. However, this means that when
, then the derivative vector is zero, and it cannot be used in for the first segment. But we will not. We immediately start with the delta of time, therefore
and the method always works.
The same applies to the end of the resulting curve, because we assign
.
and equal to the curve, so we get a beautiful acceleration. However, this means that when, then the derivative vector is zero, and it cannot be used in Quaternion.LookRotation. So yes, this approach will not work if we start withfor the first segment. But we will not. We immediately start with the delta of time, thereforeand the method always works. The same applies to the end of the resulting curve, because we assign
.In contrast to the position of the detachment, the non-ideality of its orientation at the end of the path is not important. however, we need to ensure that its orientation corresponds to the final rotation. To do this, after completion, we equate its orientation to its rotation in Y.
transform.localPosition = location.Position;
orientation = transform.localRotation.eulerAngles.y;Now the units are looking exactly in the direction of movement, both horizontally and vertically. This means that they will lean forward and backward, descending from the slopes and climbing them. To ensure that they always stand straight, we force the component Y of the direction vector to zero before using it to determine the rotation of the unit.
Vector3 d = Bezier.GetDerivative(a, b, c, t);
d.y = 0f;
transform.localRotation = Quaternion.LookRotation(d);
…
Vector3 d = Bezier.GetDerivative(a, b, c, t);
d.y = 0f;
transform.localRotation = Quaternion.LookRotation(d);Looking forward while moving
We look at the point
Throughout the path, the units are looking forward, but before starting to move, they can look in the other direction. In this case, they instantly change their orientation. It will be better if they turn in the direction of the path before the start of movement.
Looking in the right direction can be useful in other situations, so let's create a method
LookAtthat forces the squad to change orientation in order to look at a certain point. The required rotation can be set using the method Transform.LookAt, first by making the point in the same vertical position as the detachment. After that, we can retrieve the orientation of the squad. void LookAt (Vector3 point) {
point.y = transform.localPosition.y;
transform.LookAt(point);
orientation = transform.localRotation.eulerAngles.y;
}So that the detachment actually turns, we will turn the method into another corutin that will rotate it at a constant speed. The turning speed can also be adjusted, but we will use the constant again. The rotation should be fast, about 180 ° per second.
const float rotationSpeed = 180f;
…
IEnumerator LookAt (Vector3 point) {
…
}It is not necessary to tinker with acceleration of the turn, because it is imperceptible. It will be enough for us to simply interpolate between the two orientations. Unfortunately, this is not as simple as in the case of two numbers, because the angles are circular. For example, a transition from 350 ° to 10 ° should result in a 20 ° clockwise rotation, but simple interpolation will force a 340 ° rotation in a counterclockwise direction.
The easiest way to create a correct rotation is to interpolate between two quaternions using spherical interpolation. This will lead to the shortest turn. To do this, we get the quaternions of the beginning and the end, and then make a transition between them using
Quaternion.Slerp. IEnumerator LookAt (Vector3 point) {
point.y = transform.localPosition.y;
Quaternion fromRotation = transform.localRotation;
Quaternion toRotation =
Quaternion.LookRotation(point - transform.localPosition);
for (float t = Time.deltaTime; t < 1f; t += Time.deltaTime) {
transform.localRotation =
Quaternion.Slerp(fromRotation, toRotation, t);
yield return null;
}
transform.LookAt(point);
orientation = transform.localRotation.eulerAngles.y;
}This will work, but interpolation always goes from 0 to 1, regardless of the angle of rotation. To ensure uniform angular velocity, we need to slow down the interpolation as the angle of rotation increases.
Quaternion fromRotation = transform.localRotation;
Quaternion toRotation =
Quaternion.LookRotation(point - transform.localPosition);
float angle = Quaternion.Angle(fromRotation, toRotation);
float speed = rotationSpeed / angle;
for (
float t = Time.deltaTime * speed;
t < 1f;
t += Time.deltaTime * speed
) {
transform.localRotation =
Quaternion.Slerp(fromRotation, toRotation, t);
yield return null;
}Knowing the angle, we can completely skip the turn if it turns out to be zero.
float angle = Quaternion.Angle(fromRotation, toRotation);
if (angle > 0f) {
float speed = rotationSpeed / angle;
for (
…
) {
…
}
}Now we can add the unit’s rotation in
TravelPathby simply performing yield before moving the LookAtposition of the second cell. Unity will automatically launch coroutine LookAt, and TravelPathwill wait for its completion. IEnumerator TravelPath () {
Vector3 a, b, c = pathToTravel[0].Position;
yield return LookAt(pathToTravel[1].Position);
float t = Time.deltaTime * travelSpeed;
…
}Если проверить работу кода, то отряд телепортируется в конечную ячейку, повернётся там, а затем телепортируется обратно к началу пути и начнёт оттуда движение. Так происходит, потому что мы присваиваем значение свойству
Location до начала корутины TravelPath. Чтобы избавиться от телепортации, мы можем в начале TravelPath возвращать позицию отряда в начальную ячейку. Vector3 a, b, c = pathToTravel[0].Position;
transform.localPosition = c;
yield return LookAt(pathToTravel[1].Position);Поворот перед движением
Подчистка
Получив нужное нам движение, мы можем избавиться от метода
OnDrawGizmos. Удалите его или закомментируйте на случай, если нам потребуется в будущем видеть пути.// void OnDrawGizmos () {
// …
// }Так как нам больше не нужно запоминать, по какому пути мы двигались, то в конце
TravelPath можно освобождать список ячеек. IEnumerator TravelPath () {
…
ListPool.Add(pathToTravel);
pathToTravel = null;
} А как насчёт настоящих анимаций отрядов?
Так как в качестве отряда я использую простой куб, анимировать нам нечего. Но при использовании 3D-моделей для реалистичности движений нужно создать им анимации. Анимации не обязаны быть очень сложными. Для мелких отрядов стратегических игр достаточно простейших эффектов, например анимации ожидания и движения. Для смешения между ними нужно использовать Mecanim, а управлять анимациями через
TravelPath.unitypackage