Friday, 24 October 2014

Atlas Warriors, First Alpha Pre-Release

Tl;dr - First prerelease of Atlas Warriors is out, download from https://github.com/lkingsford/AtlasWarriors/releases. It's not quite finished yet.

I've opened up access to the first public pre-release of Atlas Warriors!

It is not finished yet, and shouldn't be considered to be so. There are still features missing (some minor, some glaring) and still some bugs that need fixing (again, some minor and some glaring). But it is playable, (theoretically) winnable and sometimes even fun.

But I really want to emphasise that it is still a work in progress. It still needs more stuff done before I will even consider moving it to Beta.

I finally wanted to get some feedback on how playable it is before starting to move on to attempting to balance the beast. So please - feedback away! Tell me what you like about my game, and tell me what is horribly wrong. There is an issue tracker for bugs and the like on https://github.com/lkingsford/AtlasWarriors/issues. Could you please report any minor or (far more importantly) major bugs that pop up?

You can download it from https://github.com/lkingsford/AtlasWarriors/releases. At the moment, I've only got a Windows 64 bit binary there (so if it doesn't work, that might be why).

You can also get the source from there. It's under an MIT license, so it's fairly open slather what you can do it. If you're running linux, you should be able to play it from source with Python 3.3 and Pygame. It's rl.py that contains the game proper.

If you'd like to support development financially, you can do so on https://pledgie.com/campaigns/27179 or by bitcoin (eek!) sent to 14PgnsEcgqgSrCFxTjVvczfu5Fyh85hjbU (barcode at the end of the post).

I don't think I've made it clear inside the game how some of the weapons work (although you should be able to figure it out fairly quickly). I recommend having a quick look at my previous post (http://www.nerdygentleman.com/2014/10/on-weapons.html) for a bit of a hint. You might also find the descriptions of the monsters on (http://www.nerdygentleman.com/2014/10/meet-monsters.html) to be helpful.

I'm not sure what else to say, so good luck (to both of us...)


Lachlan


PS - Bitcoin Donations - 
Bitcoin donations - to 14PgnsEcgqgSrCFxTjVvczfu5Fyh85hjbU

Tuesday, 7 October 2014

On Weapons


I have a similar philosophy for this game with weapons in that each weapon class needs to have a unique purpose. Although unlike monsters, I'm very willing to allow weapons to be incremental upgrades of other weapons.

The Weapon Classes will play differently, very inspired by Brogue. We have:

  • Daggers - You get a free counterattack when you are attacked and hit.
  • Swords - Blocking a hit with a sword allows you to parry, effectively attacking the monster.
  • Polearms - Polearms can attack two monsters in a row. At the moment, this only works when one monster is adjacent to you. I'm considering whether or not this should chance.
  • Axes - Axes are slow, but attack in a 90 degree arc. 
  • Blunt - Blunt weapons will stun any monster for one turn, if they hit.
This will hopefully provide some interesting gameplay opportunities.

Sunday, 5 October 2014

Meet the Monsters


My design philosophy (as much as I've had one) for Atlas Warriors is that everything has to have purpose. There is no need on having two different monsters that perform the same function and gameplay.

In order to do this, I do have different levels of some monsters - so (for instance) you can find Bandits, Experienced Bandits, Veteran Bandits and (hopefully never in a promising game) Bandit Warlords. Bandits are unique in being Melee characters who use weapons. There is no need to have another monster just to add a different letter and colour that does the exact same thing just may be a little harder.

As such, there are a small amount of monsters in Atlas Warriors - but they all provide a different experience.

We have (in order of appearance):

Critters - Cute. Furry. Fanged. Clawed. Actually - forget the Cute. They blindly move towards the player and attack them. Usually pretty weak.

Bandits - Men and woman who have dedicated themselves to causing crime for self interests sake. They seek out the player (and are clever enough to find the player rather then just wander in their direction), and attack the player with weapons. They get the same type of weapon effects that the player does.

Orcs - Archers from a foreign land. Orcs are reasonably strong, and have a melee attack but specialise in shooting you from afar.

Goliaths - Big. Gigantic. Brute. These horrors of gargantuan proportions are slow as they are dumb - but they can hit like a tonne of bricks and charge. They have no definition of friend or foe - they mercilessly kill anything in the dungeon and get stronger in the process.

Assassins - You think you see a shadow in the corner of the room. As soon as you turn to look at it, it's gone. You don't even feel the blade between your ribs until it is too late. Unless you are adjacent to them, Assassins are invisible when directly next to a wall or door. They've got low health, but a deadly strike.

Drakes - If it weren't for the stench of sulfur and smoke, you might consider that this midget dragon was almost cute. These breathe fire at you, and can set you alight.

Zombies - You smell the rotting flesh before you see a long dead corpse with the mission to kill. Zombies are fairly weak and have a weak attack. However, each adjacent Zombie reduces your defence significantly. Strength in numbers!

Necromancer - The first subboss. He may be skippable - if you're lucky. Raises Zombies. (I may also give him a bolt attack)

True Dragon - The second subboss. He may be skippable, but killing him will guarantee a very nice reward. This is almost the exception to my minimalism, as it really is a far stronger version of a drake. The True Drgaon will gratuitously provide rolling flames of swift death.

Final Boss - To be determined.

Friday, 3 October 2014

The Tomb of the Necromancer

I've spent the last few days redoing the monster-generation for levels. It's working reasonably well.

One of the things I've decided is to include a special undead level - the Tomb of the Necromancer. The Tomb of the Necromancer includes the titular Necromancer and Zombies. It's a regularly patterned level with lots of doors that will hopefully have players surrounded and be a sufficiently horrifying and memorable experience.





Zombies are going to be reasonably weak, but they're going to reduce your defense significantly when they're adjacent to you. You won't want too many nearby, or else you're going to be taking a lot more damage and dying a lot sooner.

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.