[.NET] A* and possibly other algorithms to come

[Farsa]

https://bitbucket.org/farsa/pathplanners

[Blequi]

I'm sure if you implement JPS and/or HPA* free of bugs, for sure this project will be a must-check to people looking for advanced/professional pathfinders.

[Puterin]

but does it really make a difference in time counted as seconds? cause if we are talking about some miliseconds it won't be any noticeable, right?

[Farsa]

@Blequi: I'm learning about the trade-offs for the algorithms. Now that I have better understanding of JPS, I'll probably provide 3 versions of it with different levels of corner cutting ability/performance. i also hope to implement other algorithms soon.
@Puterin: depends on what you are doing. Think about a game running at 60 fps, where you have 16,7 ms to run everything in your game loop.

[Puterin]

@Puterin: depends on what you are doing. Think about a game running at 60 fps, where you have 16,7 ms to run everything in your game loop.

Indeed, didn't see it that way, thx for aclaration
keep it up

[Farsa]

Current state:

PathPlanners
|-PathPlannersLib:
|-|- AStar- Implements A* as described in its Wikipedia article[1].
|-|- BestFirstSearch - Defines an abstract class of algorithms that use priority queues[2].
|-|- BreadthFirstSearch - Implements breadth-first search (BFS)[3].
|-|- DepthFirstSearch - Implements depth-first search (DFS)[4].
|-|- Dijkstra - Implements Dijkstra's algorithm[5] simply as A* with heuristic function always returning 0.
|-|- JPS - Implements Jump Point Search[6] to speed up AStar. Based on PathFinding.js[7].
|-|- JPSBB - Variation of JPS that can diagonally move between blocks.
|-|- JPSSW - Variation of JPS with stricter walking, with the goal of not cutting edges. Based to certain extent on [8].
|-|- MapReader - Provides methods for reading maps and scenarios from Moving AI Lab's benchmarks[9].
|-|- Functions - Provides default manhattan and euclidian distance functions used if other functions aren't supplied by the user when using the path planners.
|-|- PriorityQueue - Minimal implementation of a priority queue. Based on Paw Baltzersen's implementation[10].
|-PathPlannersTests - A set of unit tests. Requires downloading scenes and maps from [9] and editing the tests' source code to point to the correct directory paths.
|-PathPlannersApplication - Small toy application to test some features. Not exception safe at all

[1] http://en.wikipedia.org/wiki/A_star
[2] http://en.wikipedia.org/wiki/Best-first_search
[3] http://en.wikipedia.org/wiki/Breadth-first_search
[4] http://en.wikipedia.org/wiki/Depth-first_search
[5] http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
[6] http://grastien.net/ban/articles/hg-aaai11.pdf
[7] https://github.com/qiao/PathFinding....PointFinder.js
[8] http://www.aaai.org/ocs/index.php/SO...File/5396/5212
[9] http://www.movingai.com/benchmarks/
[10] http://stackoverflow.com/a/4019199

[Blequi]

I'm really enjoying the way it is going on.

I have a few suggestions that I think would be good to do, mostly if you'll extend this project to 3D or the many D's you want:

• Make a base class to define a Node and some virtual/abstract method to define its neighborhood, this way you'll be able to work with navigation mesh (so-called navmesh) in the future.
• Instead of using 2 bool[,] arrays to lookup your open/closed set, use 2 properties at this Node class to check it. This way you avoid how your map space is constructed ([,] implicitly means you are working at 2D space).

[Farsa]

I'll probably port some code to c++ before changing anything else, but for now the goal is really 2D grid based maps...small steps :P

[XtrmJash]

So I have been trying at A* for a while, and the only reason (I think) I haven't yet succeeded is a lack of understanding on how to go about practising. My biggest problem is that I like to see instant results, and that means I like to run in test environments. For that reason, I have been looking for a method of testing A* without implementing the Tibia maps, or any other external map provider. I want to use my own map, and I want to determine it my way. So, here is what I've done:

First off, some variables to store generic information:

        private int _rows;
        private int _cols;
        private int _tilesize;
        int[,] _mapMatrix;

These are self-descriptive. The mapMatrix will be an integer. 0 will be a start position, 10 will be the end pos, and 11 will be a blocking tile. In my program atm it uses different numbers, as there is no heuristic I use 1 as start, 2 finish, 3 wall, 4 considered, 5 path node, and 0 is a tile which has no relevance. If you see these numbers somewhere, just pretend they are correct...

Here's my map initialisation, it's pretty easy to understand once more:

        private void InitialiseMap()
        {
            // Configure our map so that we have some shit to draw by and we can change it "on the fly"
            _rows = 9;
            _cols = 9;
            _tilesize = 30; // The tile size is a pixel multiplier to determine the width of each tile
            _mapMatrix = new int[_rows, _cols]; // 1 = start, 2 = finish, 3 = wall, 4 = considered, 5 = path node
        }

Now, this bit is a little tricky. The next step is to hook the forms Paint function, which can be done by selecting the form in your IDEs design view, going to the events (normally a tab in the same place as properties) and clicking the lightning bolt (events) button. Now look for "Paint", and double click it to generate the code chunk, and add the DrawMap line from this:

        private void Form1_Paint(object sender, PaintEventArgs e)
        {
            DrawMap(e.Graphics);
        }

So, that's the hard stuff out of the way, now we can draw all we want in the DrawMap() function. Here is what mine currently looks like:

        private void DrawMap(Graphics g)
        {
            // For the X & Y coords of each tile in our map array (_rows, _cols), draw the outline of the tile
            for (int i = 0; i < _rows; i++)
            {
                for (int j = 0; j < _cols; j++)
                {
                    // Draw the rectangle.
                    g.DrawRectangle(new Pen(Brushes.Black), j * _tilesize, i * _tilesize, _tilesize, _tilesize);
                    // Switch the tiles value in the _mapMatrix and if it is a value which we believe to be a wall, start, finish, or map node, fill it
                    // Also once the tile is filled, we will mark it with the coordinates for the tile so it is easier to determine which is which
                    switch (_mapMatrix[i,j])
                    {
                        case 0:
                            g.DrawString(Convert.ToString(i) + "," + Convert.ToString(j), new Font(FontFamily.GenericSansSerif, _tilesize / 3),
                                Brushes.Black, new Point(i * _tilesize + 0, j * _tilesize + 0));
                            break;
                        case 1:
                            g.FillRectangle(Brushes.Green, j * _tilesize + 1, i * _tilesize + 1, _tilesize - 1, _tilesize - 1);
                            g.DrawString(Convert.ToString(i) + "," + Convert.ToString(j), new Font(FontFamily.GenericSansSerif, _tilesize / 3),
                            Brushes.Black, new Point(i * _tilesize + 0, j * _tilesize + 0));
                            break;
                        case 2:
                            g.FillRectangle(Brushes.Aquamarine, j * _tilesize + 1, i * _tilesize + 1, _tilesize - 1, _tilesize - 1);
                            g.DrawString(Convert.ToString(i) + "," + Convert.ToString(j), new Font(FontFamily.GenericSansSerif, _tilesize / 3),
                            Brushes.Black, new Point(i * _tilesize + 0, j * _tilesize + 0));
                            break;
                        case 3:
                            g.FillRectangle(Brushes.Red, j * _tilesize + 1, i * _tilesize + 1, _tilesize - 1, _tilesize - 1);
                            g.DrawString(Convert.ToString(i) + "," + Convert.ToString(j), new Font(FontFamily.GenericSansSerif, _tilesize / 3),
                            Brushes.Black, new Point(i * _tilesize + 0, j * _tilesize + 0));
                            break;
                    }
                }
            }
        }

So, let me take you through this a little. The object "g" is what windows uses to draw buttons, boxes, and all that jazz to the screen. It contains a few different methods which I've used. Primarily DrawString, FillRectangle, and DrawRectangle. These do not actually draw anything instantly. Instead, they wait for the form.Paint method to be called, and until that happens the changes sit in memory.

As you can see I'm cycling through 2 variables, the first is for X (i) and the second for Y (j). These represent the coordinates linked in the mapMatrix array. The mapMatrix array is only used to store information on the tiles, so we cannot modify it in this thread. That is useful as this is a display-only thread, we don't want to be changing shit in the array by mistake.

The switch statement switches the value at mapmatrix[x, y] where x and y are the coordinates determined by i and j. If the value stored against the tile is 0, it simply draws a string onto the tile displaying the X and Y coordinates of the tile. This is useful as it makes it easier to determine which tile something is happening on.

Also in the switch statement (for 1, 2, 3) you see FillRectangle. This method draws a solid block of colour. You'll notice that the method takes: A brush, X start position, Y start position, width, and height. You may also notice (if you're very observant) that I am adding 1 to the start position, and deducting 1 from the end position. This helps me to preserve the black lines of the grid which I'm drawing (fill rectangle is essentially the same as drawrectangle, and if you call fill after calling draw on the same position, the lines from draw will be overwritten).

You may also notice that each value (1, 2, 3) has a different brush colour for the fillRectangle. This again is changing the colour of each tile to show its relevance.

So, now you can begin the process of setting the values for your tiles (and modify the last chunk of code for each value type you wish to use... Heres my setStartFinish code:

        private void setStartFinish(int stx, int sty, int fnx, int fny)
        {
            try
            {
                // Reset start and finish tiles
                for (int i = 0; i < _rows; i++)
                {
                    for (int j = 0; j < _cols; j++)
                    {
                        if (_mapMatrix[i, j] == 1 || _mapMatrix[i, j] == 2)
                        {
                            _mapMatrix[i, j] = 0;
                        }
                    }
                }

                // Set start and finish tiles to values expected
                _mapMatrix[stx, sty] = 1;
                _mapMatrix[fnx, fny] = 2;
            }
            catch (Exception ex)
            {
                // This will only be thrown if it cannot draw the tiles, probably because they are OOB
                MessageBox.Show("Could not set start and end pos, check they are within the bounds of the map: " + ex.Message);
            }
        }

It just cycles through the array, finds the currently configured start and finish nodes, and when it's done that it sets the start and finish values to those passed into the function. After calling the setStartFinish function, I also call this function, to update the UI:

            this.Refresh();

The code behind my walls list is pretty simple. The walls are stored in a list box in the format: "X,Y", with no spaces, just a comma seperating out the two. That means I can split the string and parse each of the array elements returned to integers, then set the values, like so:

        private void button2_Click(object sender, EventArgs e)
        {
            // Cycle through all walls in wall list, and for each wall set the value to 3, then force a redraw
            wallsList.Items.Add(wallx.Text + "," + wally.Text);
            foreach (string st in wallsList.Items)
            {
                string[] coords = st.Split(',');
                _mapMatrix[Convert.ToInt32(coords[0]), Convert.ToInt32(coords[1])] = 3;
                this.Refresh();
            }
        }

This is called each time I add items to the list, as I want to keep the UI updated again.

So, that's pretty much all there is to it. Now you have a map array and a method of updating the display of it, also you have the general outline for how to add a heuristic. Here's what my program looks like now:

[SarahD1987]

but does it really make a difference in time counted as seconds? cause if we are talking about some miliseconds it won't be any noticeable, right?

A* search is much more efficient than breadth first and depth first search. Imagine you're at 50,50 coordinates and want to get to 45,45. With breadth first search it'd generate the following nodes and add them to a queue (50,50 would be added to the explored set):

51,50 49,50 50,51 50,49

Next it'd expand 51,50:

52,50 51,49 51,51

These nodes would then be added to the queue and 51,50 would be added to the explored set. Now your queue would contain:

49,50 50,51 50,49 52,50 51,49 51,51

Next you'd expand the nodes from 49,50 and so on.

Just imagine you're trying to map your way from say 100,100 to 500,500. Just imagine how long this would take if you were using breadth first search, because it'd also be searching down to -400,-400.

With A* search you use a heuristic. The heuristic defines how the queue will be sorted, so for example, you can sort the frontier (Set of nodes to expanded) by the distance from the goal.

For the first expansion of 50,50 you'd then sort the frontier and rather than the order of the queue being:

51,50 49,50 50,51 50,49

The order of the queue would instead be:

49,50 50,49 51,50 50,51

You'd then expand 49,50 to get:

48,50 49,51 49,49

And then sort the queue again (With the addition of the nodes expanded from 49,50)

48,50 49,49 49,50 50,49 49,51 51,50 50,51

And next you'd expand the first node in the sorted frontier.


As you can see from the example, you'd have to expand far less nodes when using A* search because the queue is sorted every time new nodes are added. If you're only looking to map over a short distance then it wont make a lot of difference with modern computers, but if you're looking to map over a larger distance, A* search is far superior.

Sorry if the post is a little confusing. It's a lot harder to explain it on here than it is in person (and being able to draw pictures!). If you want me to go over it again in more depth I can try to and I'll make some pics in mspaint to explain it a little better.


Sarah