Source: https://www.youtube.com/watch?v=QhaKb5N3Hj8&ab_channel=quill18creates
A* is a derivative of this algorithm
The algorithm touches all the nodes in the map and calculates the distance
You then know from each point what the cost is to go towards any point in the map
Normally in pathfinding we have a goal which is the green dot in the map. When we hit the green node then we get our path and then we walk back to the path along the cheapest route
A* algorithm uses a euristic to guess which direction to try to pathfinding
Source = original tile
In graphic, the edge is the line connecting two dots. You can think at the edge between two tiles.
We need to build a graph
The method below describe each individual connection between tiles.
We now need a simple custom class, a data type to hold smart data like a list of edges or neighbours or nodes.
We will add a constructor in the class that just initialises the list of nodes
We then will build our graph which is just an array of nodes corresponding to how many tiles we have in the map.
graph[x, y].neighbours.Add(graph[x – 1, y]); // add node to left
On the extreme left edge of the map we don’t have any neighbours; if x= 0 we still have an edge which is the right most node of the map. We will assume that we can’t loop around (Civilisation is for example a cylinder map game where you can loop north to south). In our case the edges are fixed and we can’t loop. That’s why we check that x > 0 to add edges on the left side.
On the right mapSizeX-1 = 9 in a map size 10 x 10.
The remaining on the Y will be basically following the same process.
Now we have a graph, a list of node. We then need to use the graph to generate some pathfinding using the algorithm in this topic.
hey you folks quitting here no welcome to another episode of our unity3d tutorial on making a tile based moving thingy like you would find in civilization or a roguelike dungeon crawler type thing we want units to move
00:11
along a map and paths find around obstacles and that sort of thing we’ve basically got everything in place for us to go ahead and write in Dijkstra’s algorithm here which will allow us to find the shortest path to a destination
00:23
so what I’m gonna do is I’m going to start translating the pseudocode into our little C sharp environment here in our move selected unit to 2 so we need one of the things we can sort of kind of need to do is translate what what what
00:40
what what what well we need the start node and the end node actually is what we need to do so if we look um where did my thing go Oh hold on I got a I forgot I got to resize this window because otherwise it’s gonna hide it every time
00:52
there we are so there clearly are some arrays this distance array and a previous array doesn’t really describe it I find that a little fuzzy sometimes you got to like figure out and backtrack to see exactly
01:06
the references but they have an array that they use that tracks the distance traveled to get to any node and what the previous note in the sequence would be so we’ve got two arrays we have to create one called dist
01:20
and ones called prep so we’re gonna go ahead and do that and what are they they are lists of nodes or they there are dictionaries they’re not there we go they’re not list they are dictionaries where we can pass a node we can say
01:30
something like hey the distance to some node is equal to 10 or whatever reason so we want that sort of structure so it’s going to be a dictionary where the key for the dictionary is going to be a node and the value for is going to be a
01:51
float for a distance and we can initialize this new dist – how’s it doing that I’m here okay new dictionary we’re gonna need another one which is going to be very much the same dictionary the key is going to be a node
02:11
and the value is going to be another node and this is going to be prove previous new dictionary this one here all right we’ve got those set up now what it wants us to do is it wants to set the distance for source to be zero
02:29
and the previous node for source to be unidentified or undefined which is null source in this case is where we’re coming from note that there’s no goal right now source is where we’re coming from well we are coming from where our
02:43
current unit is well we know we have our selected unit and it’s got a component on it called unit which has a tile X and tile why right so our source art yeah the source help call it that our node source is from our graph
03:07
it’s our graph at coordinate tile X comma tile Y I’m going to do this as a one-liner because we can make it maybe look a little fancier if we say it’s our graph at tile
03:22
X ily like so that’s our source that’s where we’re coming from so in our dictionary which right now is empty which is fine we’re gonna populate we’re gonna say distance source obviously the source is zero distance
03:40
from itself to go from the source to the source it’s zero and prev this is a an array that or a dictionary that contains the chain of nodes you have to walk to you to go from one tile to the other well the way you walked from source well
03:57
there’s no previous it’s it’s the end of the line there’s nothing more early in the chain than the source our original tile so we just set that to no undefined is null in c-sharp okay now we’re alright now we’re gonna
04:08
keep going to the next line let me maybe you should rank if I this a little bit like that so now we have some sort of loop or each vertex named V in graph well we’re using the word node right but nodes our vertexes vertices that’s fine
04:25
so we can say hey we’ve got a for each keyword construct whatever you want to call it here for each nud fee in graphs or graph we can do it that way well we sort of have it doesn’t can we look through it that way we don’t have to do
04:43
a or x equals 0 y equals 0 thing we might be able to rate it through this we’ll see if it works out if we do this actually it’s see do we get a syntax error know everyone’s hunky-dory okay that is
04:58
good to know all right so for each vertex in graph we’re going to see if if V is not our source then oh this is where we initialize so we’re initialize everything you have infinity distance
05:22
since we don’t know any better right now also it’s possible that some nodes and be reached from the source which would make infinity our reasonable value so what we’re gonna do is we’re gonna populate the array we’ve already
05:50
populated the source one and then we’re gonna populate the others technically we didn’t have to do this here we could have done it here as an else but that’s gonna be fine so we’re gonna set the dist it be equal to we do have an
06:02
infinity that’s handy which is this just sets it to the highest possible float I think and then we’re gonna say previous of vo really–it’s prep here in previous here wikipedia what are you doing to me we’ve
06:19
got a prep in a previous you’re killing me is it previous everywhere else its previous everywhere else Wow that’s unbelievable I’ll keep it prep because that way we have two
06:32
four-letter words there and there’s some four-letter words I want to say whoever wrote this stuff up so we’re gonna say no you know we don’t know what note comes before it in the chain I think it’s pretty obvious like we didn’t
06:43
necessarily need to set this here we could have set this all inside of here and whatever it’s fine and then we’re gonna add V to Q what is Q cues our list of unvisited nodes okay and literally it will just be a list all right so let’s
07:00
go ahead and set up one of those up over here and I set up a list of nodes and I’m gonna call it unvisited these are nodes we haven’t checked yet new list of nodes so set up the queue the list of nodes we haven’t checked yet right so
07:24
that every node we haven’t checked yet will be inside of unvisited and we’re gonna do that here we’re going to add our unvisited dot add B note that everything gets added to that including our source right so everything gets
13:48
yeah we’re gonna need that information when we create all our nodes it’s kind of annoying no that’s just the reality of it though okay public int X public int y so when we loop through all of our nodes over
14:10
here we’re gonna have to say listen graph X Y dot x equals x our nodes have to be self-aware over their position because then what I can do to make a little helper function over here public distance – it’ll need another node
14:30
called an maybe oh it will return a float and what it’s going to do is it’s going to return the distance between the two I wonder if it’s faster if I just use the the vector 2 helper sure return so vector twos got a helper called
14:49
distance which is going to do the math for us and it needs it needs two vectors pass back into it so we’ll say vector one is going to be our current XY and vector2 is going to be the secondary nodes x and y so this will return the
15:11
distance between two nodes so if we go way back down here we’ve got our zero distance plus our node u dot distance to V now we do have to talk about something again is this the way we want it this is gonna
15:29
return the Euclidean distance between two nodes remember way early on in the first video I hit play yeah as I say it’s probably going to crap out on me here and just return right away don’t actually run
15:47
there we go what is the correct distance from here to there it depends on your game right this will return the Euclidean distance which is gonna be the square root of two which is what 1.1 yada yada yada yada so right
16:05
now it’ll tell me the distance from here to here will be 1.2 which may or may not be correct now note that for pathfinding purposes the distance here is not the same necessarily as the movement cost I can leave it in here
16:18
that way it’ll generally prefer going in straight lines because one of the weird things that can happen let’s say I’m trying to path fine from this tile here oh yeah from this pot of tile here to this tile here if the movement cost for
16:31
diagonals is just equal to 1 in the pathfinding system it’s entirely possible the pathfinding system will suggest we do something like wigle wigle wigle wigle wigle wigle wigle wigle wigle
16:41
and technically that will take just as many turns as if we just go on straight to the left and then up one but it would look stupid so I’m gonna go ahead and accept the fact even though in my game I’m gonna have them move on the
16:56
diagonals and have it only cost one point of movement even though that’s the case I am going to have this distance to still return the actual Euclidean value just because it will tend to return paths that are straighter and use less
17:12
diagonals it’ll look better but it entirely depends on your game exactly how you want to work this but I’ll leave it in for now ok so we are gonna grab this new calculation we’re gonna stick it in this thing called alt and then
17:25
we’re gonna check to see this is the value based on the current path we’re walking again the first time still weird because we’re currently in you know we’re just looking at the first node but at this point we’re bumping into a new
17:35
node or we’re bumping into a node and we want to see is the distance based on the current path we’re working out is it shorter than any distance that’s already been calculated for this node so if alt is less than the distance of this new
17:49
node then what we’re gonna do is we’re going to set this as the new distance to this node and we’re gonna say this node which maybe we already had a path but this is a shorter path the shortest way for the
18:04
node to work is through you so what we’re doing is a situation is it’s gonna run it is gonna run so we’re we’ve got some source and we’ve got you know some tile over here and somehow maybe we’ve already bumped into this tile but we
18:19
went some crazy route and it’s got a cost of like ten well now we’ve just have to calculate a slightly different route over here that makes it slightly cheaper to go this way it only has a cost of eight so now we’re telling it
18:30
that from this node instead of this being the previous right which could happen on various sneaky paths and depending on how diagnose cost instead of saying that from here like this is the previous node in the chain we’re
18:41
gonna say no from here this is the previous node in the chain because it’s a slightly shorter distance so we’re gonna go ahead and update that. That brings us to the end of the if and then the end of the four and then the end of
18:54
the while
and then this by default returns the full set of all distances and all previous nodes it calculates from our source node. So basically what the distance is to every single node in the entire map but that’s not what we want.
19:12
we can stop following the pseudo code now and what we can do is actually look at this particular discussion over here if we are only interested in the shortest path between vertices source and a target we can terminate the search at line 15 if u equals target so let’s talk about that. Do we have a target well yes so we have a source node which is this one we can also at this point create a target node and a target node this one:
Out of all the unvisited nodes we grab the one with shortest distance still left in there and if u == target then we can break out of the while loop.
In the for each loop below, if we haven’t found a u yet then we set it to the possibleU;
22:59
faster way to check for possible nodes among the unvisited one, possibly still ways to optimize it but honestly this is probably as fast as it goes so u is going to be the unvisited node with the smallest distance. First time through the only thing that (23:18) has a non infinite number is going to be our source then after that everything that’s neighbored to our source will get a new distance calculated so the second time through, what it’s going to be doing is grabbing one of our 23:31 neighbors and putting that in and so on and so forth. so u is gonna be the unvisited note the smallest distance. if we happen to find u is equal to a target we can break out of the while loop;
23:45
so at this point if we get here then either we found the shortest route to our target or there is no shortest or there is no route at all to our target which is possible.
How do we check to see if there’s no route at 24:18 all to our target?
If distance of our target is infinite no route to our target or actually a better thing because I don’t like comparing floats if prev of our target is null then there’s 24:40 no route that goes from our target that can backtrack to our source and that’s the thing; this list will be kind of inverted these prevs will basically; you start at our target and go back step through all those things until you get 24:51 back to the source and that will be how you get there. there’s no route between target and the source so probably we just want to return.
25:06
but then we get to this point and we know we have a legal route to our target so what are we going to do? well what we’re going to want is another list of currentPath.
25:19
since we know we have a legal path we’re going to loop through each one of these targets 25:42 and add them to our current path. Our current path. we’re going to set a new gonna be a list of nodes and then we’re gonna make a new placeholder, some sort of new node curr node which is going to start at our target 26:02 while curr is not equals null while there’s still a previous node to step backwards through we’re going to add curr to our current path
26:55
our path describes a route from our target to our source so we need to invert it which we can do very simply because we still have that link component so we can usereverse
29:48
okay so here’s the question we’re looping through a list of neighbors and we’re checking the distance to the neighbor the only thing that could be happening here is if you
30:01
neighbors is now oh right of course of course of course of course we populate the neighbors here
and we’re adding stuff based on the graph well we could be adding stuff here that are not initialized because it only gets 30:13 initialized.
here so we actually have to loop twice.
30:33
so yeah we were putting a bunch of nulls inside of this neighbor array.
31:17
should be happening is we should now have a path again it is worth noting that everything that we’re doing is based sort of on the predicate that there is only one unit.
31:58
We can give a path to a unit like that now it doesn’t know what a node is is a class
Then list node will belong to the class Node and no more to the Tilemap
32:19
– my map data what I could do though is I could make it public and then this actually becomes I’ll map dot node oh it doesn’t know what a list is because we didn’t include generic
33:43
so after we calculate the path we give the unit the new calculated path
34:01
so by the end of it either it will fail in which case we’ll just jump out here
which means the path will still be just set to null because it’s got no way to get there or we’re gonna go and set it to the current path
34:15
to get there in the next video what we will do is we will have our unit actually step through this path step by step now note at this point we are going to be ignoring mountains so if I go and I click here the unit should go one two
Lesson 6
00:21
What we’re gonna do is actually draw some lines to show what the path was. We will use debug draw line for that which will mean 00:34 by default that I’m only show up in the scene 00:45 but it’s going to work great for our purposes here so we’ll get to see what our actual path is 00:56
In our unit code what I’m going to do is there if it’s got a path I’m gonna get it to draw lines because as you may recall from the last episode when we click a tile we generate a path from our map script, the tile map Cs script 01:34 generates a path and then stores it in the units current path.
so what we’re gonna do is we’re gonna draw lines based on that however before we do that something I hadn’t quite clicked in yet the unit has a tile X and 01:48 tile Y and this is used when we actually do our clicking way down here; so this is the the code that generates the path for the unit and it’s generating to a destination which is the 02:03 tile we clicked on
well it starts based on where the units current position is right right over here the source node where we start path finding
from is selected unit tile X tile Y which are these two variables over here
02:17
but if we go and jump into the game I click on unit over here and I hit play you can see the tile X and tile Y never gets set; it just stuck at zero even though it’s current position on the screen is five five
so we got to go 02:30 ahead and assign that not only that but we will actually need a reference to the map in here
just like how in our clickable tile here
we have a reference to the map we’re also you need a reference the map in the unit because 02:45 the unit will need to call our function here
which converts tile coordinates to world coordinates so we’re gonna go ahead and do a little bit of that right now so, in our unit we’re gonna create a public tile map map reference
and then 03:00 in tile map way at the top in the start we’re gonna make sure to set up the selected units variables which is so in selected unit it’s got a get component unit which has a tile X and we’re just gonna feed 03:20 that in the selected units transform.position dot X we’re just going to set it to there we’ll do the same thing for the Y
so this way in the editor I can position the selected unit anywhere and it’ll have the x and y tile 03:35 coordinates that are appropriate there and then the last thing we need to do on our selected unit is it wants to know what the map object is and the map object is simply this
which means every 03:51 time we were testing our path finding every single time we were calling generatePathTo
we are generating a path from the zero zero coordinates.
Now let’s go ahead and start drawing the line so we’re gonna have our update function back so we draw it every single frame and what we’re gonna use is debug dot draw line 04:16 now we only want to draw a line if we actually have a path so first if current path not equals null (okay so we know we actually have a path)
what are we gonna have? well current path is a list of nodes and the node is basically it’s a 04:30 special custom class that we built .
05:32 so we’ve got a node class here and our node class it has a list of tile coordinates node it has an x and y
so what we’re gonna do and current path is just a list of those nodes so we just have to 05:45 step through those one at a time and draw a line from one node to the other on the screen easy peasy. so we need to track what our current node is when I start at zero
and we’re gonna loop through them all now we want to loop 05:59 until we sort of run out of nodes which logically might be something like current node is less than current path dot count
but we have to remember that we actually have to end slightly sooner because what we’re drawing is a line 06:12 from one node to another if you’ve got, let’s say you had three nodes in total that’s actually just going to be two lines from the first to the second and second to the third so we actually have to end a little bit sooner than that 06:23 because in here we’re gonna say we’re going to be using debug draw line (draw line not draw ray) and draw line need to start at an end vector so what we need is vector three start and vector three end 06:41 and start will simply be the node we’re currently on and end will be the next node which is why we got to make sure to cut out just a little bit sooner.
So this is the reason we needed the map object and in the map object we wrote a function in 06:53 there a very simple one that converts the tile coordinates to world coordinates because our draw line needs world coordinates but we have tile coordinates so it needs an X and a Y in here as a function we wrote earlier so 07:04 that’s pretty simple it’s our current path [current node] dot X and then the same thing with the Y
and then the second line is the same thing except it’s going to be the next node
We can now do debug draw 07:52 line from start to end
BUG: our a transform position x and y are both floats and we’re trying to stuff them into an int and it always
Parse
08:39
it’s pretty important when you do a while loop actually increment your little number over there
08:54
we click well we get to click but oh no we do get the line just we can’t see it and say it’s inside of our blocks over here if we turn on the gizmos it’s there but 09:07 it’s really hard to see oh it doesn’t help that the line is green as well okay we can change the color
09:38
case you’re gonna be screwed we’ll use something else I don’t know if blue would be better I have no idea we’ll use a we’ll use red and the other thing we want to do is right now this is returning something with a Z of 0
so 09:54 what I’m going to do is I’m going to add in on both of these a vector which gonna have a zero zero one hopefully that’s the right direction 10:08 it’s so like so just to try to bring it forward. I sent it backwards okay and negative and now it should be in front
we don’t have any code in here to take into account the fact that we can’t through walk through mountains or the fact that swamps are difficult to walk through nothing of the sort also we are currently using the four-way 10:47 connection so it’s not going to do any diagonals but it’s potentially may be calculating paths whereas these sorts of paths are really easy to work out because there’s nothing particularly tricky about them when you’re trying 10:59 when you don’t have to avoid anything we could have used simple a simple arithmetic to work out these sorts of lines to get somewhere so let’s go ahead and complicate up our map a little bit by making it so that you can’t walk 11:11 through mountains
so we’re gonna pop into our cod; in our path finding generatePathTo we have one little bit right in here
which calculates the
11:27
distance to the next node from one neighbor to the other it figures out what the distance is now this works technically but what we’re thinking what we’re trying to work on 11:43 here is we don’t actually care about the distance what we are interested in is what is the movement cost to enter the next tile which depending on your game might just be the distance but in a dungeon crawler or civil like game it’s 11:58 often not the distance in particular with diagonals usually the cost is one even though the distance will be the square root of two is the actual distance to go diagonally from this center of the tile to this center of the tile;
the actual cost in most games will be one and then the other thing is if you’re entering something like swamp even though the distance is the same from this tile to this tile as this tile to this tile the cost might be twice as 12:25 much because it’s difficult terrain
I really should put the Node class in a separate file let’s go ahead and do that
Node has now got its own class
Let’ now create a new method in TileMap called cost to enter tile and it will simply want a coordinate and X into y now it’s some games Direction might matter right the question might be what’s the cost to walk from one tile to another for example in a game of civilization where you have rivers between tiles entering a tile from one direction might just be a normal cost might just cost one however entering from the other direction where you’re crossing over a river might cost 2 so you might need to worry about some of that here we’re going to ignore that
we’re going to assume the cost to enter a tile is the same regardless of what you’re going of where you’re going.
So now what is the cost enter tile well we have our list of tiles and we know so tile XY is of certain tile type, so we have all of our tile types tiles XY returns an index to this array so we have our tile what’s it called tile type tt equals that so what is the cost to enter this tile we don’t really 15:01 have that information right now
here’s my tile type info
obviously we’re going to need to put something like that in there
so let’s go and give it a public float going to be something like movement cost 15:19 that’s probably default one
so here what we’re gonna do is to return tt.movement cost very simple now we’re gonna have to fill in those informations
so if we go into Unity and we go into our map that’s where we define all of our tiles well grasslands having a movement cost of one is fine and say maybe our swamp has a movement cost of two and our mountains it’s you can’t enter it now I could have 15:43 a boolean here that just makes it non enterable
and that might make it super clear or I could literally just do something like
this it is so expensive that it’s effectively infinite um I think that’s fine but again you 15:57 could in here have a boolean that says can be entered of course the other thing to keep in mind is movement types if you can have a game where you have flying units walking units maybe hovering units then the movement cost 16:10 might vary based on that unit in which case you need a slightly more sophisticated setup but for our personal example here this is going to be completely sufficient.
so we’re going to return the movement cost enter the tile
16:21
Now here we have our alt which is our distance to move into that tile so it takes all of our current distance up to this point
16:41 and then adds some amount
now right now we’re using dist to we’ll leave this line in here will comment it out but instead what we’ll use is we’ll use cost to enter tile we’re going to add the cost to enter the tile of V
17:20
avoiding mountains we’re passing around our mountains
also what’s really interesting wonder if there’s a breakpoint; you can see there so here you’re trying to get to this tile it’s like okay I’ll charge through the swamp
but if you go a little bit further it’s like “I’m gonna avoid these two tiles of swamp I’m gonna go around it because it costs too much”
that is pretty cool and in fact here the shortest route to get to this point 17:47 would have actually been you go here slightly shorter it saves a couple of tiles right but because of the swamp because the swamp penalty here it decides to take the long way around here because this is technically faster even though it’s longer because we don’t have to walk through the swamp
and so what we have here is not a shortest path algorithm what we have here is a least cost algorithm at least movement cost algorithm and that’s pretty damn good
18:13
I will provide a couple of caveats though one consideration that our system ignores is the fact that especially in games like civilization the cost to enter difficult terrain isn’t as straightforward as you might imagine in civilization especially civilization 5 right if you if you have a hill a hill has movement cost of 2 and most units have a movement cost or a movement point of 2 they can move 2 tiles per turn but a hill counts as 2 tiles it costs 18:43 you 2 movement;
if our character is here if this was a hill adjacent to us if our character moved onto the hill that would use up both his movement points and the unit would then have to stop that would be the end of his turn
18:54 however if the hill were here the unit could first move into this grassland which would cost him one point he would have one point remaining and then he’d still be able to enter the hill tile
because in Civilization 5 as long as you 19:10 have any movement left whatsoever you can always enter rough terrain it’s fine now this is a contrast to some of the older tile based strategy games where it didn’t work that way instead if you didn’t have enough movement to enter you couldn’t enter it would use up whatever movement you had and sort of give you credit for it for the next turn so for example if you had if you had a unit with a movement of one that was next to a hill that’s a let’s say the hill had a 19:38 cost of three on the first turn of trying to enter it you just bump up against it and it would do nothing
on the second turn you’d bump up against it it would do nothing on the third turn though you would have accumulated enough progress into that tile to finally enter it our current system would successfully do pathfinding for that second example where you’re sort of bumping into the difficult terrain and then eventually getting there however it would not properly take into account the Civ five style of movement where you can always enter difficult terrain as long as you have any movement left or whatsoever and we’d have to change things around in that our cost calculations right over here the the cost to enter tile;
cost enter tile would actually have to be aware of how much movement your character would likely have when you got to this place because if you are trying to enter a mountain or a hill which normally cost two but you only had one movement left well it’ll only 20:34 effectively cost you one movement to get into that tile as opposed to if you got there and you had to movement then it would cost you to movement and civilization five the path fighting system does take that into account.
The other thing to note in those types of games as well is we generate the path when you click on the tile but is there anything that can happen that might invalidate the path well what if someone moves into the tile that you are trying 20:59 to get into or moves into your way somewhere along the path. what do you do about that? do you recalculate constantly? in Civ five I believe they only invalidate your path if someone moves into your ultimate goal, the tile you’re ultimately trying to get into or if someone it is in your way of the next tile you’re gonna move into if so if you’ve got a long path let’s go back to the picture and again in Civ 5 I’m pretty sure if this would work;
so we’ve got our path that goes along here if you know I start walking here and then at some point someone walks into this square over here
I don’t believe it will instantly stop our unit in Civ five however if we had progressed all the way over here and we were about to enter that square and someone was there I think then it would cancel our path finding at that point but in Civ 5 and again I’m pretty sure this way it works if at any point anyone who ever walked into our end path at that point we would also set our current path to null and once again prompt the player for movement.
so little things like that you constantly have to consider it so let’s have an issue if you don’t have one unit per tile because a lot of times you can walk through other units although sometimes that’s only friendly units what if it’s an empty units all kinds of things like that to consider so what I want to do is 22:11 I want to go and put in our 8 way movement at this point because right now we’ve got these sharp corners and really I really wanted to have the 8 way movement.
So that’s fine we can easily do that we generate our graph over here
and 22:23 right now we’re generating a a four-way graph
so if X is greater than 0 then in addition to allowing the movement to the left we’re also going to try to move 23:28 left and up and left down which is going to require checking that we are not at the top or bottom so if it’s greater than 0 then we can move to the left and if the Y is greater than 0 not only can we move to the left but we can 23:41 also move left and down and if the Y is less than the upper bounds would be left and up.
we’ll do the same thing here or the direction towards the right 23:59
we should be able to pathfinding lawn along diagonals
You can notice one weird thing going on here 24:33 what is this should it not logically be shorter for our character to walk at once it reaches at this point here shouldn’t he go straight here
well there’s a good reason why he’s not doing that; the reason is in our current 24:48 model the movement cost to move from here to here is one
and the movement cost to move from here to here is also one
and in civilization and in most tile-based roguelike kind of dungeon crawlers that’s true moving diagonally 25:02 still just cost you one even though yes technically it’s a longer distance in most games like you know what it’s fine diagonals will just cost one who cares so this is this is a perfectly legal and logical move but it looks stupid so how do we avoid this looking stupid?
in our calculation for cost to enter
all we’re doing is figuring out the cost to enter the tile regardless of where you’re coming from but what if we did consider where we were coming from? and simply added a tiny extra cost for diagonal movements just a little to break ties and that’s the problem here there’s a 25:52 tie and the game is just not necessarily picking the thing that we would most likely want as a tie resolution and depending on how you order your neighbors when you generate your neighbors here:
when you generate your neighbors depending on what order you generate your neighbors in this can actually will have an impact on the tiebreaking but let’s go ahead and make it a little bit explicit by just goofing around so we’re 26:16 gonna say source X source Y int target X int art target Y so the cost is basically going to be just the target
so float cost equals
this and we’re returning cost but if source X is different from the target X and the source Y is different from the target Y
27:02
we are moving diagonally fudge the cost for tie-breaking
all we’re gonna do is add a miniscule extra amount to the cost when you’re moving diagonally and this should cause it to prefer straight lines as opposed to diagonals it’s purely a 27:24 cosmetic thing
and that’s the thing with a lot of pathfinding stuff and a lot of things in computer games there’s a way to do things that is technically correct but 27:39 if it doesn’t feel right to the player then that is not a success so we have to change where we are using the cost enter tile
we have to make sure to specify the source tile which is U.X and u.y
there we go so now if we 27:55rerun this example and we click here you can see it now prefers to go in a straight line
everything else is the same and you know the movement either way is perfectly legit and legal movement but now prefers 28:07 to go in a straight line it feels better.
it’s still interesting still takes a long way around avoids that Marsh if I click there it’ll do that way
if I click here whoa it actually goes all the 28:17 way around
interesting which is actually different from before before we had diagonals which allow us to shave a lot of corners off when I click down here it actually preferred to go this way go on to the swamp 28:30 completely and now if I do this it actually doesn’t dodge the swamp completely anymore but the reason is it doesn’t actually have to move through that many swamp tiles because it can move diagonally what if I do this ah 28:39 it actually dodges one extra swamp tile
it’s technically the shortest path and this is probably what you’d want to do it looks a little bit silly to dart around that way but it cuts down 28:52 it cuts out one whole swamp tile and remember swamps cost 2 so it’s got all that pathfinding put in there that’s pretty good now what you can do is to actually move your character around well that should be pretty obvious.
we could put in some sort of next turn button and then every time you click it in your unit over here
every time the next turn button is clicked we just change our position
to the next node on the path and we’d 29:16 probably remove it.
So let’s go ahead and do that let’s let’s go and say something like void moveNextTile
we know from our line drawing it’s pretty clear that the first thing in our current path array is the tile we’re actually standing on and 29:49 the last one is our destination so if we want to move to the next tile what we have to do is first of all let’s get rid of the old first so remove the old current / first node from the path
30:08
so current paths.remove at zero now grab the new first node and move us to that position.
so its current path at zero, the new zero, this is the new first path obviously we’re gonna have to put in 30:35 some error checking over here, if current path equals no return right away so we remove the first node then
So the current path will have an x and y coordinates so what we need to do is we need to translate this to the world so we want to set our transform position to be where, map dot tile coordinate dot world coordinates and 31:10 we’re going to feed in the tile coordinates which is simply a current path 0.X and currentpath 0.dot y and now we’re going to be at the new position
on the off-chance if current path dot count is equal to 1 we only have one 31:33 tile left in the path and that tile must be our ultimate destination so let’s just clear our path finding info.
32:06 because remember the tile that is our destination is on the path finding; the case here would be there’s two nodes left
we enter here in MoveNextTile() and there’s two nodes left the one we’re currently standing on and the next 32:19 node which is our ultimate target so first remove the one we’re standing on then we move ourselves to the sole remaining node
which is our ultimate target and then that means our count is 1 which means current path equals null, we’re done with you no need to have you any more
I’ll go ahead and create a UI button
it’ll create a canvas and event 32:45 system and give me a button over here if we take this and anchor it to say the the bottom-right corner of the screen
and we say move forward
and all we’re going to do our button is will add a new thing that 33:03 listens to the event
we’ll just hard code it to our unit
and our unit script has a moveNextTile function
so every time I click the button that move forward unit 33:19 moveNextTile script will be executed and we should move forward so let’s go ahead and give that a try and click here and we’ll hit move forward move forward and move forward move forward move forward move forward 33:30 move forward that’s great note however we are moving exactly one tile per turn which may or may not be correct right we don’t know unit we’ll need some sort of movement rate maybe it can move more
33:43
than one tile per turn yada yada yada and then we have to keep in mind how our movement mechanics are supposed to work like our discussion with CIV before I mean we can do something like this we can say something like movement or move 33:57 speed equals to hey will do will do civilization so every time we move we can move up to two tiles
so we need to add a while loop. While remaining movement speed is greater than zero (remaining movement is equal to movement speed)
34:15
we’re going to repeat our previous stuff like that
so right now we would move two squares per click let’s test that first that should definitely be the case so if 34:34I click anywhere it should move two squares so it should end this up right there uh-oh; mistake
things I always forget to do, we have decrement our movement is what I was going to say now right now I’ll go ahead 34:52 and I’ll just decrement it by one we’ll just do minus minus because I we have to remove the actual movement cost
but let’s go ahead and give this test we’ll do that I’ll hit the button we should end up there there 35:04 we go now we should end up there great
now the problem is it doesn’t work because if we were working if we’re trying to walk through the swamp it will end up here now if I click this button swamp has a 35:15 movement cost of two so right now it’ll go straight to the end and that is obviously incorrect
so what we have to do instead of just removing one we have to remove map.cost…oh it’s not public 35:30 let’s make it public
It’s also worth noting as afloat and yeah in something like civilization 5 while the absolute movement speed of your character is an integer you can actually use up partial amounts of 35:45 movement along the way so we’ll make this a float
we’ll do this so map.costToenterTile and we’re moving from our current spot which 36:05 is this
to our next spot which is that
we’re currently standing on this zero zero
which we then remove
and we are going to the next one
which is will be the new zero hereafter this one’s removed but as currently this one one
so zero is our current spot one is our next spot so we could figure out 37:07 the cost from one to the other then we move us to the other and then we remove the original first tile and there we go. will but out of this function if ever we run out of it counts or run out of stuff to path find or if we run out of 37:21 movement will also drop out of this function
I’m never updating my my units current tile position I’m never updating that which I need to do so we set a position here but we also have to say a tile X is equal to that pile Y is equal to this and for the sake of I think it might be a little bit cleaner
38:58 because I didn’t actually specify that you you literally can’t walk in a mountain it’s technically viable it’s just gonna cost me what like 99 billion movement points to go into there but that’s technically possible it’ll always try to avoid the mountains but yeah I suppose then with that in mind I have to go I was aiming for like minimalism but in our tile type we’ll have to add a boolean public boolean is walkable I have a default of true
39:30 our map will make the mountain not walkable so the movement cost at this point literally doesn’t matter here I’ll switch it back to one it may it should make no difference
we’ll have to make a couple of change to cost enter tile method in TileMap.cs; line 67,68:
but it still has the problem where if we click on the mountain it’ll still path find into that so we have to choose where we disallow the path finding. I could have it in generate path to method
could out not allow that to happen there or we could have it a clickable tile whereas if you’re trying to click into a tile you can’t move into it just dies. We will update TileMap.cs creating a new bool method
Another thing you could do is you can change this around so you can click on tiles that you can’t legally enter and instead you just try to path line as close as possible and basically the way you would do that we 43:10 wouldn’t put in this filter
and we’d know that the final node would have an infinite cost so you could path fine to it you can click on the mountain it’ll generate a path that leads you to the mountain and then in your unit movement 43:20 script in here
when you check the cost enter tile if the cost is infinite you could just but out at that point that would bring you as close to possible as something that you’re not allowed to enter without actually entering it right. which could be handy hope that made i hope that was clear this video has already gone on way too long so we’re gonna have to put in a cut but if i check now i can indeed if I click on a mountain it cancels the the path finding completely otherwise everything continues to work perfectly well anyway I think that brings us to the end of this tutorial
This is debug information if I turn off gizmos or if you export this project right even with gizmos turned on that’s only within this editor if you export this project to the web or to Windows or whatever this debug line-drawing will not show up in it you’re gonna have to figure out your own way to draw a line maybe you want to use the line renderer.
This project works in turn-based obviously but it could perfectly well work in real time as well there’s nothing stopping this from happening in in absolute real-time what you would 44:47 do here in your Unit.cs basically inside of your update from time to time you would call move next
you can also and this is one of the things is maybe you don’t want your unit to teleport forward you actually want to have it 44:59 look like it’s sliding from one direction to the other which you can do as long as like this move forward button would actually become a next turn button you click that and what would happen is your unit instead of instantly 45:13 teleporting to the end location would just move over time from one to the other you’d probably update your tile X tile Y right away
but your position you could just have some sort of lerp or average; you can go from one to the other you can have an animation time.
