Sunday, 7 September 2014

A* Pathfinding in Python

I thought the following might be helpful to some of you. It's a snippet of code in Python to perform A* Pathfinding.

I've been avoiding writing it for ages, but have been yet again impressed by how little Python gets in the way of what I'm doing. I remain impressed by the language.

Again, method was found on http://www.policyalmanac.org/games/aStarTutorial.htm

It's reasonably well commented, and should slot it fairly easily into any grid-based environment. It doesn't support weighting yet - but it would be trivial to add (include the weight when adding distance for g).

I apologise for my inconsistent naming conventions. I started the project with no idea about Python, and the A* had to fit into that dodgy area. Essentially, you'll have to replace self.x and self.y with the starting potion and replace reference to self.currentMap.Walkable with where to get a boolean value of the walkability of the position.

And again, this is released under my modified UnLicense:
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.


    def GetRoute(self, dest):
        # Performs an A* search to find route to go somewhere
        # Input:
        #   x, y - from self.x and self.y
        #   self.currentMap.Walkable(x,y) - returns if can walk at x,y
        #   dest - (x, y) tuplet of destination
        #
        # Returns a list of (x, y) tuplets
        # 
        # From <http://www.policyalmanac.org/games/aStarTutorial.htm>
        # 1) Add the starting square (or node) to the open list.
        # 2) Repeat the following:
        #   a) Look for the lowest F cost square on the open list. We refer to this as the current square.
        #   b) Switch it to the closed list.
        #   c) For each of the 8 squares adjacent to this current square 
        #      If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.           
        #      If it isn't on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square. 
        #      If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.
        #   d) Stop when you:
        #      Add the target square to the closed list, in which case the path has been found (see note below), or
        #      Fail to find the target square, and the open list is empty. In this case, there is no path.   
        # 3) Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.
        
        # ORTH_DISTANCE and DIAG_DISTANCE are for weights of travelling between the cells orthogonally
        # and diagonally respectively. If diagoanal is further in game, then DIAG_DISTANCE should be 14
        # As the distances are the same in mine, they're weighted evenly
        ORTH_DISTANCE = 10
        DIAG_DISTANCE = 10
        
        # Heuristic for calculating h is Manhattan Distance - 
        #   abs(pos.x - dest.x) + abs(pos.y - dest.y)
        
        # OpenLists consists of tuplets with (
        #   [0]: Position.x, 
        #   [1]: Position.y,
        #   [2]: ParentPosition.x, 
        #   [3]: ParentPosition.y,
        #   [4]: g (distance to get here from parent),
        #   [5]: h (heuristic distance to destination) )
        OpenList = [(self.x, self.y, self.x, self.y, 0, abs(self.x-dest[0]) + abs(self.y-dest[1]))]     
        ClosedList = []
        while (len(OpenList) > 0 and (len([k for k in OpenList if k[0] == dest[0] and k[1] == dest[1]]) == 0)):             
            # Find entry in OpenList with lowest F score
            # F = G + H                     
            Current = min(OpenList, key=lambda i:i[4]+i[5])         
            OpenList.remove(Current)
            ClosedList.append(Current)
            Active = [(Current[0] - 1,  Current[1],     Current[0], Current[1], Current[4] + ORTH_DISTANCE, abs(Current[0] - 1 - dest[0])   + abs(Current[1] - dest[1])),
                (Current[0] + 1,    Current[1],     Current[0], Current[1], Current[4] + ORTH_DISTANCE, abs(Current[0] + 1 - dest[0])   + abs(Current[1] - dest[1])),
                (Current[0] - 1,    Current[1] - 1, Current[0], Current[1], Current[4] + DIAG_DISTANCE, abs(Current[0] - 1 - dest[0])   + abs(Current[1] - 1 - dest[1])),
                (Current[0] + 1,    Current[1] - 1, Current[0], Current[1], Current[4] + DIAG_DISTANCE, abs(Current[0] + 1 - dest[0])   + abs(Current[1] - 1 - dest[1])),
                (Current[0] - 1,    Current[1] + 1, Current[0], Current[1], Current[4] + DIAG_DISTANCE, abs(Current[0] - 1 - dest[0])   + abs(Current[1] + 1 - dest[1])),
                (Current[0] + 1,    Current[1] + 1, Current[0], Current[1], Current[4] + DIAG_DISTANCE, abs(Current[0] + 1 - dest[0])   + abs(Current[1] + 1 - dest[1])),
                (Current[0],        Current[1] - 1, Current[0], Current[1], Current[4] + ORTH_DISTANCE, abs(Current[0] - dest[0])       + abs(Current[1] - dest[1] - 1)),
                (Current[0],        Current[1] + 1, Current[0], Current[1], Current[4] + ORTH_DISTANCE, abs(Current[0] + dest[0])       + abs(Current[1] - dest[1] + 1))]
            for i in Active:
                # If point not in closed list and is walkable
                if (len([j for j in ClosedList if j[0] == i[0] and j[1] == i[1]]) == 0) and self.currentMap.Walkable(i, True):
                    # Look for point in open List
                    Candidate = [j for j in OpenList if j[0] == i[0] and j[1] == i[1]]
                    # If point not in open list                 
                    if(len(Candidate) == 0):
                        # Add point to the open list
                        OpenList.append(i)
                    else:
                        # Otherwise, check to see if this path to the square is shorter, using G. If so, replace square with current route (changing parent and g) 
                        if Candidate[0][4] > i[4]:
                            OpenList.remove(Candidate[0])
                            OpenList.append(i)
                
        # If no path found, return empty route
        if len([k for k in OpenList if k[0] == dest[0] and k[1] == dest[1]]) == 0:
            return []
        else:
            # Add path to route
            Route = []  
            CurSquare = [j for j in OpenList if j[0] == dest[0] and j[1] == dest[1]][0]
            # Iterate until we reach the starting point
            while (not(CurSquare[0] == CurSquare[2] and CurSquare[1] == CurSquare[3])):                 
                CurSquare = [j for j in (OpenList+ClosedList) if j[0] == CurSquare[2] and j[1] == CurSquare[3]][0]
                Route.insert(0, CurSquare)
            return Route

Friday, 29 August 2014

I don't want to set the world on fire


TL;DR version - Scroll to the bottom for cool fire spewing animations

I've spent the last days adding at least a basic animation framework, and a fairly cool animation to Atlas Warriors. As a test, I added a blue shimmer when a Healer heals another enemy - which worked just fine but isn't particularly interesting.

The primary reason I wanted it was for implementing Dragons. What is a dragon without some good and proper fire breathing? So, without further ado...

FUS RO DAH!

Lame, I understand - but at least it wasn't another Arrow In The Knee reference

The first step was an algorithm for determining flame coverage over the area fired. That algorithm can be used (with the actual distance) for determining who to ignite, and (by looping the distance from 0 to the actual distance) for creating the animation.

The algorithm is far more simple then what I've probably made it. My pseudo code also probably gives away that I'm a lawyer - not a compsci or programming major... so I hope you can at least understand it. Also know that some was more trial and error'd then well planned. This is sure as hell not best practice!

  • Given:
    • Source
    • Target
    • Desired Distance
    • Desired Radius at distance
  • Calculate angle between Target and Source
  • Calculate the end point ( end(x,y) = (sin(angle) * distance, cos(angle) * distance) )
  • Calculate angle to the other end points. The other end points are separated by 1 unit, perpendicular to the end point, in distance radius in each direction. Put the angles in list J
  • Create a 2D array (G) initialised to zero from [-distance,distance][-distance,distance]
  • For i in J
    • For k := 1 to Distance
      • x = sin(i) * k
      • y = cos(i) * k
      • If x,y blocks flame then break
    • xpart = frac(x + .5)
    • if (xpart < 0) then xpart = xpart + 1
    • ypart = frac(y + .5)
    • if (ypart < 0) then ypart = ypart + 1
    • xint = floor(x + .5)
    • yint = floor(y + .5)
    • G[xint,yint] = G[xint,yint] + xpart/8 + ypart/8
    • G[xint+1,yint] = G[xint,yint] + (1-xpart)/8 + ypart/8
    • G[xint+1,yint+1] = G[xint,yint] + (1-xpart)/8 +(1-ypart)/8
    • G[xint,yint+1] = G[xint,yint] + xpart/8 + (1-ypart)/8
  • Return G
This returns a grid showing how much flame hit each section. That G will have some fractions where only part of a square was hit by the flame. I'm going to use those fractions as the chance of igniting a monster on those tiles. I also use them in the animation.

A sensible person (including possibly me in the future) would: leverage whatever antialiased line algorithm they had access to (including, for instance the pygame ones), do the drawings of a black line on a white surface and use the darkness as the percentage of the square hit. I may still migrate to this in the future. It does still have to be looped to have the collision detection.

The animation is quite simple. As described already, the above algorithm is looped from 0 to the desired distance. For each frame, it loops over the grid and draws a character in a foreground color  and a background color all selected to reflect the value. Mine use > 3, >2, >1, >.75, >.5, >.25, >0.15 and > 0. It does nothing on a 0.

The end result is reasonably good, if not yet perfect. I will note that it will be coming from Dragons - not from the player as in these gifs. They will hopefully be sufficiently horrifying when you have an encounter with them!







Any comments would be appreciated.

Saturday, 23 August 2014

Better Levels, and 'Second Wind'

Since the last post, I've been working on two things. Firstly, I've made the levels more interesting. I've made heavy adjustments to how it plans new rooms, and added the possibility of rooms interconnecting.

I've also added a 'Kill or be Killed' mode (which is essentially the Second Wind mode from  Borderlands). One of my goals has been to keep the figures (like HP and damage) low. Having Kill or be Killed allows me to keep the figures low and make the game a little more harsh knowing that a player will often be able to get themselves back.

The game is never going to be the greatest roguelike - but I'm hoping it'll be a bit of freely available fun. It's also proving to be a good learning exercise.

Not looking forward to trying to balance it though.






Wednesday, 20 August 2014

Atlas Warriors


I've been spending some time working on a Roguelike in Python. It has been so far confirmed to be completable, but way incomplete and unbalanced.

The goal is for a game to be completable in 30 to 60 minutes.

I'm experimenting with a couple of things that will hopefully work out well. I've got an interesting system for calculating accuracy comparing the attackers to hit. Secondly, I've got a heal-on-exploration mechanic where you only replenish health as you explore more areas. I'm trying to keep the numbers nice and low (including HP) - so I'm hoping that levelling up might be almost treated as a method of healing.

Some screens are below



More news will (probably) follow.

Thursday, 14 August 2014

Python - Parsing XML to Object

My apologies for it having been a while.

In the course of programming a roguelike in Python, I wrote the following chunk of code which might be helpful to others. Given a filename of an XML file and a constructor, it parses the XML file and uses the constructor to fill the object with the contents of the XML file (so - a field called 'SPAM' in the XML file would automatically populate the variable SPAM in the object created by the constructor). If the variable is a boolean or integer, it'll copy the XML as such.
import xml.etree.ElementTree as ET

def parse(filename, objectConstructor):
    tree = ET.parse(filename)
    root = tree.getroot()
    items = []
    for i in root:
        item = objectConstructor()
        for j in i:
            t = item.__dict__[j.tag]
            v = j.text
            if isinstance(t, bool):
                v = v == 'true'
            elif isinstance(t, int):
                v = int(v)          
            item.__dict__[j.tag] = v
        items.append(item)
    return items
    

Wednesday, 10 April 2013

Roundspace Prototype



I made this little prototype last night. It still needs tweaking for maximum "fun", menus, sound, better graphics etc - but this was a 1 bit of night prototype. For what it is, I'm actually happy, and I enjoyed playing it. 
Find it at https://dl.dropbox.com/u/46145976/Roundspace.zip
Any feedback? Anything you'd change?
If it doesn't work - you may need the .net distributable - http://go.microsoft.com/fwlink/?LinkId=199021 and the XNA distributable - http://go.microsoft.com/fwlink/?LinkID=148786. It'll probably work anyway.






Friday, 22 February 2013

Range Calculation Code - New Version


My old range calculation code (found here) was, as I admitted, slow and... well... rubbish.

Completely rewritten. Almost no trace of the old code whatsoever, and I do it in a far, far, far simpler manner now.

Again - licensed under Lachlan's Very Public License, being a modified Unlicense. Do whatever you want with it, don't blame me if something goes wrong, and donations/attribution/a comment saying its useful would be really nice.


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

            int[,] distances = new int[range * 2 + 3, range * 2 + 3];
            for (int ix = 0; ix < distances.GetLength(0); ix++)
            {
                for (int iy = 0; iy < distances.GetLength(1); iy++)
                {
                    // -1 is not yet visited
                    // -2 is a collision point
                    distances[ix, iy] = (PlayerCollides ?
                                        (CheckCollision(ix + start.X - range - 1, iy + start.Y - range - 1)) :
                                        (TileCollides(ix + start.X - range - 1, iy + start.Y - range - 1))) ?
                                        -2 : -1;
                }
            }

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

            distances[range + 1 ,range + 1] = 0;            
            
            for (int i = 1; i <= range; i++)
            {
                for (int jx = -i; jx <= i; jx++) { for (int jy =  -i; jy <= i; jy++)
                {
                    if (distances[jx + range + 1, jy + range + 1] == -1)
                    {
                        int minDistance = int.MaxValue;
                        for (int lx = -1; lx < 2; lx++)
                        {
                            for (int ly = -1; ly < 2; ly++)
                            {
                                if (!(lx == 0 && ly == 0))
                                {
                                    int distance = distances[jx + range + lx + 1, jy + range + ly + 1];
                                    if (distance >= 0)
                                    {
                                        minDistance = Math.Min(minDistance, distance +
                                            (((lx == 0) || (ly == 0)) ? STRAIGHT_COST : DIAG_COST));
                                    }
                                }
                            }
                        }
                        if (minDistance != int.MaxValue)
                        {
                            distances[jx + range + 1, jy + range + 1] = minDistance;
                            if (minDistance <= (range * STRAIGHT_COST))
                            {
                                returnlist.Add(new coord(jx + start.X, jy + start.Y));
                            }
                        }
                    }
                }}
            }

            return returnlist;
        }

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;
        }

Wednesday, 13 February 2013

A* Pathfinding


Work is still progressing (between study and work-proper) on Roguelikish.

I've added A* pathfinding. As a result, you actually do some path finding to move when you click somewhere, and your party isn't quite as stupid when trying to follow.

I figured since I'd done it, that the pathfinding 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.
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.

I've attempted to implement the A* algorithm as described on A* Pathfinding for Beginners. There's probably bugs. Diagonals are costly (they cost 1.4 x the movement of verticals).  The comments are probably old, inaccurate, or just plain wrong and probably shouldn't be relied on. The programming style is amateur, but it works.

The function provides a list<coord> of the path to take to reach coord end from coord start.

Any questions - I may or may not be able to answer. I implemented the algorithm, but only mostly understood it.


//Required classes
    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 class workingPathVertex : IComparable<workingPathVertex>
    {
        public coord V;
        public int G;
        public int H;
        public int F() { return G + H; }
        public workingPathVertex parent ;
        public workingPathVertex(coord _V, workingPathVertex _Parent, int _G, int _H)
        { 
            V = _V;
            parent = _Parent;
            G = _G;
            H = _H;
        }
        public int CompareTo(workingPathVertex that)
        {
            return (that.F() > F()) ? -1 : 1;
        }
    }

//Functions
//Relies on two 2d boolean arrays - which can fairly easily be written out.
//One is CheckCollision(int, int) which returns whether the tile can be collided 
//  with - and whether the thing on the tile can be collided with. So - players 
//  would make it return to
//The other is TileCollides (int,int) which returns whether the tile can be
//  collided with. Behaviour is controlled from "playercollides" arg
//Some debugging codes still in there, and the comments are old, barely updated
//  and possibly flatly wrong.

public List<coord> GetPath(coord start, coord end, bool PlayerCollides = true)
        {
            List<workingPathVertex> openList = new List<workingPathVertex>();
            List<workingPathVertex> closedList = new List<workingPathVertex>();

            workingPathVertex startV = new workingPathVertex(start, null, 0, Manhatten(start,end)) ;                  
            workingPathVertex V = startV;

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

            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);
                        if (PlayerCollides ? (!CheckCollision(i.X,i.Y)) : (!TileCollides(i.X, i.Y)))
                        {
                            openList.Add(new workingPathVertex(i, V, V.G + (((ix == 0) || (iy == 0)) ? STRAIGHT_COST : DIAG_COST), Manhatten(i, end)));
                        }
                    }
                }
            }

            openList.Remove(V);
            closedList.Add(V);

            bool finished = false;
            bool succeeded = false;
            workingPathVertex endVertex = null;

            bool surroundtarget = false;

            if (PlayerCollides ? (CheckCollision(end.X,end.Y)) : (TileCollides(end.X, end.Y))) {                 
                surroundtarget = true;
                bool surroundPossible = false;
                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);
                            surroundPossible = (PlayerCollides ? (!CheckCollision(i.X, i.Y)) : (!TileCollides(i.X, i.Y))) || surroundPossible;
                        }
                    }
                }
                finished = !surroundPossible;
            };

            //This is lazy looping I know, but it's late, and I'm tired, and it should work
            while (!finished)
            {


                V = openList.Min();
                openList.Remove(V);
                closedList.Add(V);

                ////Debuggy stuff
                //Console.WriteLine("ITERATION:\n V moved is " + V.V.X.ToString() + "  " + V.V.Y.ToString());
                //Console.WriteLine("OPEN LIST:");
                //foreach (workingPathVertex Z in openList)
                //{
                //    Console.WriteLine(Z.V.X.ToString() + "\t" + Z.V.Y.ToString() + ") " + Z.F() + "\t" + Z.G + "\t" + Z.H);
                //}

                //foreach (workingPathVertex Z in closedList)
                //{
                //    Console.WriteLine(Z.V.X.ToString() + "\t" + Z.V.Y.ToString() + ") " + Z.F() + "\t" + Z.G + "\t" + Z.H);
                //}


                if (!surroundtarget)
                {
                    if ((V.V.X == end.X) && (V.V.Y) == end.Y) { finished = true; succeeded = true; endVertex = V; };
                }
                else
                {
                    if ((Math.Abs(V.V.X - end.X) <= 1) && ((Math.Abs(V.V.Y - end.Y) <= 1))) { finished = true; succeeded = true; endVertex = V; };
                }


                //Find lowest F
                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);
                            workingPathVertex closePath = closedList.Find((f) => { return ((f.V.X == i.X) && (f.V.Y == i.Y)); });
                            if ((closePath == null) && (PlayerCollides ? (!CheckCollision(i.X, i.Y)) : (!TileCollides(i.X, i.Y))))
                            {
                                workingPathVertex iPath = openList.Find((f) => { return ((f.V.X == i.X) && (f.V.Y == i.Y)); });                                
                                if (iPath != null)
                                {
                                    //If iPath is already on openList                                
                                    int GviaV = V.G + (((ix == 0) || (iy == 0)) ? STRAIGHT_COST : DIAG_COST);
                                    if (GviaV < iPath.G) { iPath.G = GviaV; iPath.parent = V; }
                                }
                                else
                                {
                                    //If iPath is not on the openlist
                                    iPath = new workingPathVertex(i, V, V.G + (((ix == 0) || (iy == 0)) ? STRAIGHT_COST : DIAG_COST), Manhatten(i, end));
                                    openList.Add(iPath);
                                }
                            }
                        }
                    }
                }
                if (openList.Count <= 0) { finished = true; }
            }

            if (succeeded)
            {
                //Console.WriteLine("SUCCESS: ");
                List<coord> path = new List<coord>();

                workingPathVertex nextVertex = endVertex;
                while (nextVertex != null)
                {
                    //Console.WriteLine(nextVertex.V.X.ToString() + " " + nextVertex.V.Y.ToString());
                    path.Add(nextVertex.V);
                    nextVertex = nextVertex.parent;                    
                }
                path.Reverse();
                path.RemoveAt(0);
                return path;
            }
            else
            {
                //Console.WriteLine("FAILED");
                return null;
            }

            

        }

        //Calculates manhatten distance
        int Manhatten(coord A, coord B)
        {
            return (Math.Abs(A.X - B.X) + Math.Abs(A.Y + B.Y));
        }
    }
Edit (12.29AM 13/02/2013 AEDST) Fixed Bug

Monday, 28 January 2013

Roguelike...ish


Bit further along. Borrowed more David Gervais and Angband tiles.

There is now mouse control, 4 PCs and random rooms filled with Orcs and Skeevers. No combat yet though.

Basic idea is a Party Based, Short (aiming for 1h long) Roguelike. Probably with optional permadeath.

Thursday, 17 January 2013

Random Dungeons


I don't know what I want to do with it, but I'm enjoying it.

Saturday, 12 January 2013

Random Dungeon Generation Attempts



They're not perfect, but my first attempts in a while of Random Dungeon/Level Generation. I've used a BSPish process (see http://roguebasin.roguelikedevelopment.org/index.php?title=Basic_BSP_Dungeon_generation). 





Friday, 24 August 2012

ADOM Resurrection

I'm trying to get a bit of support for what is one of my top 3 games of all time (with Portal 2 and Grim Fandango): ADOM, or Ancient Domains of Mystery as it tends to be known to its friends.

ADOM is one of the biggest roguelikes that there has been historically (in fact, so big that it even had its own newsgroup), and differs from most other roguelikes in its consistency of atmosphere and storyline. Fwiw - a Roguelike is a generally text-graphics based RPG game, generally with randomised dungeons, permanent death and a ruleset fairly inspired by Dungeons and Dragons. They also tend to be hard. Really hard.

Biskup's already got the base $48000 raised, and is currently up to $52268 as of writing with 7 days remaining. If it hits $55000, he'll commission a full tileset (sample below). Beyond that, there will be more races and classes added ($60000), a hopeful Steam/Desura version ($65000) and beyond that further quests.



I'd really love to see this make it to at least getting Chaos Knights as a class!

Can I encourage anyone remotely interested to check it out?

The campaign page is on http://www.indiegogo.com/resurrect-adom-development


Lachlan

Saturday, 14 July 2012

TBA Progress



Progress. It's beginning to look and feel kind of Gamey!

I'll be referring to it as "Starship" for now until a final name is picked. Assuming that I keep going with it.