MELHARFI 2D Game Engine - 20. AStar Pathfinding

Repos

MELHARFI-2D-Game-Engine.

20. AStar pathfinding

AStar (A*) pathfinding

AStar is an algorithm developed by many persons, you can find many version along your search, for me i pick one from a sample and i extract just the logic from it and do some changes:

Cleaning old version from stuff not needed and make it simpler to use.

Old version needs that the matrix should be square like 50 * 50 or 120 * 120 grid, and never 50 * 30, to resolve that problem, I have just marked the other spaces as obstacles to be ignored.

Old version take the matrix information from a file, and not by code, now you can push a matrix directly by code.

Old version used a reversed orientation when pushing the matrix, you must give the Y value followed by the X Value, now i reversed this method to give X followed by Y.

What A* do ?

Well it just give you a way point, from a start position until the end point,

For that you must give a grid called matrix, and in that grid must contain information about each cell call a nods.

The cells could be in 4 states

Walking node = 0

Water node = 1

Fire node = 2

Wall = 3;

How to use it ?

You should add a using reference to using MELHARFI.AStarAlgo;

After that you need to initialize the Matrix

This is all the code documented.

                        
using System;
using System.Drawing;
using System.Linq;
using System.Windows.Forms;
using MELHARFI.Manager;
using MELHARFI.Manager.Gfx;
using MELHARFI.AStar;
using System.Collections.Generic;

namespace _2dProject
{
    public partial class Form1 : Form
    {
        // (a new instance of the MAP that hold the grid inside) not initialized yet
        private Map map = null;
        //(a list that hold the pathfinding node, that we should clear each time we generate a new path)
        private List shortestPath = new List();

        public Form1()
        {
            InitializeComponent();

            Manager manager = new Manager(this, "CORE_ENGINE");
            manager.Background = Color.WhiteSmoke;

            
            //we create a grid that hold the information of our map, as obstacles (players, walls ...)
            // for ex we'll take a X = 7, Y = 8 grid :

            byte[,] byteMap = new byte[7, 8];
            for (int i = 0; i< 7; i++)
                for (int j = 0; j< 8; j++)
                    byteMap[i, j] = 0;  // all nodes is initialized as marked as walked nodes for the moment

            // first we initialized the grid that hold the obstacles
            // to make some nodes as not walking, simply mark them as obstacle:
            byteMap[2, 0] = 3; // in the column (X) 2, and line (Y) 0 there is an obstacle

            // generating map depending on the matrix
            // Start Point is (0,0) and end Point is (3,0), and the matrix of the map as 5th argument
            map = new Map(7, 8, new MapPoint(0, 0), new MapPoint(3, 0), byteMap);
            shortestPath.Clear(); // we clear the waypoint/pathfinding nodes

            // new instance of AStar class that take our map as argument to handle it
            AStar AStar = new AStar(this.map);

            // we generate the waypoint with the CalculateBestPath() function
            List sol = AStar.CalculateBestPath();

            // we put the result in the sol List
            if (sol != null) this.shortestPath.AddRange(sol);
                sol.Reverse();
            
            #region show result
            string data = "";
            foreach (MapPoint mp in sol)
                data += "(" + mp.X + "-" + mp.Y + ") ";

            MessageBox.Show(data);
            #endregion
        }

    }
}

The sol.Reverse(); make sure that the result is reversed because the result is from the endpoint to the start by default, or we wanted it to be from start to the end.

Sol has now 5 nodes with it's there X, Y positions and i let you the way you extract the information as you fit.