It’s used to find the next set of tiles we can try and walk on. What this does is that, given a particular tile (and the target tile), we want to get all the tiles around itself. The next thing we need to do is a little helper method. These are tiles that we will essentially work on. We populate the “ActiveTiles” with our start block. And we create a list of “ActiveTiles” and “VisitedTiles”.In our example we use a list of strings but this grid or map can be made up any way you like. Set up the “map” which is essentially a grid.Start.Y = map.FindIndex(x => x.Contains("A")) įinish.Y = map.FindIndex(x => x.Contains("B")) We set up some basic code : static void Main(string args) Inside our main method (We are doing this inside a console app but you are welcome to edit this to your needs). Parent is just the tile we came from to get here. How many tiles we’ve moved so far + how many tiles we think it will probably take to reach our goal. It’s useful later on because given a set of tiles, we work out which one to “work on” by ordering them by the CostDistance. CostDistance is essentially the Cost + the Distance.This is worked out using the SetDistance method where it’s basically, ignoring all walls, how many tiles left/right and up/down would it take to reach our goal. Distance is the distance to our destination (e.g.If it was two tiles to the right, it would be a cost of 2 etc. So for example if this is right next to the starting tile, it would be a cost of “1”. Cost is how many tiles we had to traverse to reach here.X,Y are locations on a grid that we will use.Or in simpler terms, given a map, starting at one location, what is the most efficient way of getting to a second location, walking around walls, obstacles and ignoring dead ends.įor example if we had a map that looked like so : It probably makes sense to rewind a little bit and ask, what exactly is the A* algorithm? A* Search is a path finding algorithm. So I thought I would quickly whip up a post on a dead simple implementation of the A* path finding algorithm in C#. C# can be a bit weird in that for business applications, you can find a million examples on how to talk to Sharepoint, but when it comes to AI, Machine Learning, or even just data structures and algorithms in general, it can be a bit bare. I remember many moons ago, as part of the Google AI Challenge (ended a few years ago which is a real shame), I actually swapped my solution to use Java just so I could use an A* search algorithm that I found on the internet. If you’ve ever taken part in an AI challenge or contest over the years, you’ve probably had to work out a path finding algorithm along the way.
0 Comments
Leave a Reply. |