Sunday, 17 February 2013

Not Quite A* Movement Range Calculation

Update - 22/02/13 - 
Turns out this code really really did suck. Don't use it. I've completely rewritten it, actually using a little thought rather then misappropriating a poorly chosen algorithm and trying to shove it in.

The new one is on here


I looked at A*, then made something similar to calculate ranges of movement. This code is so you can determine the locations that a character can move to, knowing where collisions are and the like. You will have to provide functions CheckCollision and TileCollides, and probably change a couple of other things to make it work for you. Comments are pretty much non existent, and the code works  but isn't optimised or very fast.

Again, I figured since I'd done it, that this code could be useful. It's released under the following license:


Lachlan's Very Public Licence - which is a slightly modified Unlicense
This is free and unencumbered software released into the public domain.
Anyone is free to copy, modify, publish, use, compile, sell, or distribute this software, either in source code form or as a compiled binary, for any purpose, commercial or non-commercial, and by any means.  
In jurisdictions that recognize copyright laws, the author or authors of this software dedicate any and all copyright interest in the software to the public domain. We make this dedication for the benefit of the public at large and to the detriment of our heirs and successors. We intend this dedication to be an overt act of relinquishment in perpetuity of all present and future rights to this software under copyright law. 
If you use the source, the Author (Lachlan Kingsford) would actually like to know - but it's by no means necessary. Feel welcome to provide a copy of what you do via email, or comment on www.nerdygentleman.com. Attribution is also nice and appreciated, but again, by no means necessary. Donations via paypal are also nice. 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.


    public class coord
    {
        public int X;
        public int Y;
        public coord() { X = 0; Y = 0;  }
        public coord(int _X, int _Y) { X = _X; Y = _Y; }
        public static bool operator==(coord first, coord second)
        {
            return ((first.X == second.X) && (first.Y == second.Y));
        }
        public static bool operator !=(coord first, coord second)
        {
            return !((first.X == second.X) && (first.Y == second.Y));
        }
        public override bool Equals(object O)
        {
            return (coord)this == (coord)O;
        }
        public override string ToString()
        {
            return "(" + X.ToString() + ", " + Y.ToString() + ")";
        }
    }

    public class workingRangeVertex// : IComparable<workingRangeVertex>
    {
        public int G;
        public coord V;
        public workingRangeVertex parent;
        public workingRangeVertex(coord _V, workingRangeVertex _Parent, int _G)
        { 
            V = _V;
            parent = _Parent;
            G = _G;
        }
        public override string ToString()
        {
            return V.ToString();
        }
    }

 public List<coord> GetRange(coord start, int range, bool PlayerCollides = true)
        {
            List<workingRangeVertex> openList = new List<workingRangeVertex>();
            List<workingRangeVertex> closedList = new List<workingRangeVertex>();

            workingRangeVertex startV = new workingRangeVertex(start, null, 0);

            openList.Add(startV);

            const int STRAIGHT_COST = 10;
            const int DIAG_COST = 14;            

            while (openList.Count() != 0)
            {
                workingRangeVertex V = openList[0];
                {
                    openList.Remove(V);
                    closedList.Add(V);
                    for (int ix = -1; ix < 2; ix++)
                    {
                        for (int iy = -1; iy < 2; iy++)
                        {
                            if (!(ix == 0 && iy == 0))
                            {    
                                coord i = new coord(V.V.X + ix, V.V.Y + iy);
                                workingRangeVertex closePath = closedList.Find((f) => { return ((f.V.X == i.X) && (f.V.Y == i.Y)); });
                                if (closePath == null)
                                {
                                    if (PlayerCollides ? (!CheckCollision(i.X, i.Y)) : (!TileCollides(i.X, i.Y)))
                                    {
                                        int cost = V.G + (((ix == 0) || (iy == 0)) ? STRAIGHT_COST : DIAG_COST);
                                        if (cost <= range)
                                        {
                                            workingRangeVertex openPath = openList.Find((f) => { return ((f.V.X == i.X) && (f.V.Y == i.Y)); });
                                            if (openPath == null)
                                            {
                                                openList.Add(new workingRangeVertex(i, V, cost));
                                            }
                                            else
                                            {
                                                openPath.G = Math.Min((V.G + (((ix == 0) || (iy == 0)) ? STRAIGHT_COST : DIAG_COST)), openPath.G);
                                            }
                                        }
                                    }
                                }
                                else
                                {
                                    closePath.G = Math.Min((V.G + (((ix == 0) || (iy == 0)) ? STRAIGHT_COST : DIAG_COST)), closePath.G);
                                }
                            }
                        }
                    }
                }
            }

            List<coord> returnlist = new List<coord>();
            foreach (workingRangeVertex V in closedList)
            {
                returnlist.Add(V.V);
                Console.WriteLine(V.V.X.ToString() + ", " + V.V.Y.ToString());
            }
            return returnlist;
        }

1 comment:

  1. OK... in hindsight, this code needs a lot of optimization. I've got a second idea of how to do it which I'll try soon.

    ReplyDelete