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:
Code:
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:
Code:
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:
Code:
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:
Code:
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:
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:
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:
Code:
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: