Sub's coding pool party

[sub]

Ah, thanks. I'm not really sure how I could go about adding humor to the game, although I do think it will need something to give it some personality. The graphics right now are downright terrible, although I'm not really in a position to improve them. I saw this talk a little while ago and it really demonstrates how it's the little things that makes a game great.

http://www.youtube.com/watch?v=Fy0aCDmgnxg&feature=player_embedded

With that in mind, I decided to make some promotional art for the game. Brace yourselves people.

This grim scene depicts a fierce battle that took place between the Red and Yellow nations. The Red Empire strikes down the last yellow foe as a soldier in the neighboring yellow hex covers his eyes, unable to watch the fall of his comrades.

I'm considering making this the loading screen for my game. Currently the game loads instantly, though, so perhaps I'll add in like a 3 minute delay when you start the game where I just show this screen with the words LOADING pasted in the lower left.

I don't think anyone will believe me, but I did this in 3 minutes on my laptop with nothing but a touchpad. I don't know how it's possible for so much talent to exist within one person. It shouldn't be possible.

edit: Perhaps when the game starts up, a message will appear that asks if you're Skyrider. If you answer no, it will proceed to the game as usual. If you answer yes, that loading screen will pop up for 6 minutes. Also, your units will have a 40% chance of disappearing every turn.

edit 2: And also for Sky, there will be nuclear silo silos on the map that are capturable only by enemy AI. These will spawn nuclear bombs every turn, that can strike anywhere and instantly kill everything in that hex and every adjacent hex to the targeted hex.

edit 3: Actually, now that I think about it, that sounds awesome.

 

[sub]

So I need to do the AI, and in order to do the AI, the game needs to be able to move units around the map in a path that makes sense. So I started working on figuring out how astar pathfinding works, since astar is the most popular and widely touted as the best pathfinding algorithm out there.

So I made an attempt at it and it kind of works. Originally I thought it was working, but as I played around with it some more, it became apparent that it's a bit ****ed up right now. Made a quick video to show off it sucking

http://www.youtube.com/watch?v=tU6FDlCRXk8&feature=youtu.be

So it sometimes backpeddles or will move in a zig zag. I'm going to take a look at it tonight and see if I can get it working properly.

 

[sub]

I've figured out the problem, or at least one of the problems. The GScore for everything was coming out to either a 9 or a 13. It turns out that it was calculating the GScore of elements which were set to their default value on the array, which was -1, hence the 9 or 13's. I should have passed the parent tile to the determineGScore function, and instead I was passing the tile I wanted to get the GScore of. Easy fix for that.

It's working close to perfectly, but it'll still still a tad bit wonky. It'll find close to the shortest path, but zig zag a bit too much I think. Haven't got the foggiest idea why.

If anyone wants to try it out, here's a link. It was originally a hastily thrown together version of Conway's Game of Life, and then became a messy version of Snake, and then kind of morphed into this, so the program is kind of held together with scotch tape and prayers. The pathfinding part is fine, but it will probably crash if there's no way to get to the place it's trying to go.

https://sites.google.com/site/subcreationsdownload/home/Sub AStar Attempt.7z?attredirects=0&d=1

And I guess I'll also paste the code for the pathfinding part
Pathfinding.h

#ifndef PATHFINDING_H
#define PATHFINDING_H

#include "constants.h"

class Board;

class Pathfinding 
{
private:
    int OpenList[NUMBER_OF_CELLS_ON_GRID][2];
    int ClosedList[NUMBER_OF_CELLS_ON_GRID][2];

    int FScore[NUMBER_OF_CELLS_ON_GRID];
    int GScore[NUMBER_OF_CELLS_ON_GRID];
    int HScore[NUMBER_OF_CELLS_ON_GRID];

    int FinalPath[NUMBER_OF_CELLS_ON_GRID];

    int StartLocation, GoalLocation;
    int OpenListIndex, ClosedListIndex;
    
    int SelectedTile, SelectedTileIndex;

    int NumberOfTilesOnOpenList;
    int NumberOfTilesOnClosedList;


public:
    Pathfinding();    

    void findPath(int start, int goal, Board &aBoardObject);
    
    void resetVariablesToStartNewSearch();
    
    void addAllAdjacentNodesToOpenList(Board &aBoardObject);
    void addSelectedTileToClosedList();

    bool isTileOnOpenList(int TileToCheck);
    bool Pathfinding::isTileOnClosedList(int TileToCheck);

    int determineNeighboringTileNumber(int index, int WhichNeighbor, Board &aBoardObject);

    int determineFScore(int index, int ParentIsWhichNeighbor, Board aBoardObject);
    int determineGScore(int Parent, int ParentIsWhichNeighbor);
    int determineHScore(int index, Board aBoardObject);

    int FindLowestFScoreOnOpenList();

    bool determineIfGoalIsOnClosedList();

    void printBug();

    int getFinalPath(int index);
};
#endif

Pathfinding.cpp

#include "pathfinding.h"
#include "board.h"

#include <iostream>
#include <fstream>

using namespace std;

Pathfinding::Pathfinding()
{
    StartLocation = 0;
    GoalLocation = 0;

    SelectedTile = -1;
    SelectedTileIndex = -1;

    OpenListIndex = 0;
    ClosedListIndex = 0;

    NumberOfTilesOnOpenList = 0;
    NumberOfTilesOnClosedList = 0;

    int counter = 0;

    while (counter < NUMBER_OF_CELLS_ON_GRID)
    {
        OpenList[counter][0] = -1;
        ClosedList[counter][0] = -1;

        OpenList[counter][1] = -1;
        ClosedList[counter][1] = -1;
        
        FScore[counter] = -1;
        GScore[counter] = -1;
        HScore[counter] = -1;

        FinalPath[counter] = -1;

        counter++;
    }
}

void Pathfinding::findPath(int start, int goal, Board &aBoardObject)
{
    resetVariablesToStartNewSearch();

    StartLocation = start;
    GoalLocation = goal;

    //add starting location to open list
    SelectedTile = StartLocation;
    SelectedTileIndex = 0;

    OpenList[0][TileIndexDimension] = SelectedTile;
    OpenList[0][ParentDimension] = SelectedTile;
    NumberOfTilesOnOpenList++;
    OpenListIndex++;

    //set g score for the starting location and initialize the other two to invalid numbers
    GScore[SelectedTile] = 0;
    HScore[SelectedTile] = 9999;
    FScore[SelectedTile] = 9999;

    //initialize that shit
    ClosedList[0][1] = 0;

    bool IsGoalOnClosedList = false;
    while (IsGoalOnClosedList == false)
    {
        //Get next tile to try
        SelectedTile = FindLowestFScoreOnOpenList();

        //look at each adjacent tile, adding the ones not on the open list or closed list to the open list
        addAllAdjacentNodesToOpenList(aBoardObject);

        //move the tile we just found from the open list and put it in the closed
        addSelectedTileToClosedList();

        if (determineIfGoalIsOnClosedList() == true)
            IsGoalOnClosedList = true;
    }

    //find the ending tile on the closed list
    int counter = 0, ClosedIndex = 0;

    while (counter < NumberOfTilesOnClosedList)
    {
        if (ClosedList[counter][TileIndexDimension] == GoalLocation)
        {
            FinalPath[0] = ClosedList[counter][TileIndexDimension];
            ClosedIndex = counter; // used in saving the path below
            counter = 9999;
        }

        counter++;
    }    
    
    //save the path
    bool Continue = true;    
    int index = 0, PathSize = 0;
    while (Continue == true)
    {
        index++;
        PathSize++;
        
        ClosedIndex = ClosedList[ClosedIndex][ParentDimension];
        FinalPath[index] = ClosedList[ClosedIndex][TileIndexDimension];
        
        if (FinalPath[index] == StartLocation)
            Continue = false;
    }

    
    //reverse path
    int Beginning = 0;
    int End = 0;

    int tempindex = NUMBER_OF_CELLS_ON_GRID - 1;
    counter = 0;
    
    while (counter < tempindex)
    {
        Beginning = FinalPath[counter];
        End = FinalPath[tempindex];
        
        if ((End != -1))
        {
            FinalPath[tempindex] = Beginning;
            FinalPath[counter] = End;
            counter++;
        }
        tempindex--;
    }
    
    printBug();
}

void Pathfinding::addAllAdjacentNodesToOpenList(Board &aBoardObject)
{
    int AdjacentTileCounter = 1;
    int AdjacentTile = -1;

    ofstream myfile;
    myfile.open ("Scores.txt");

    const int NUMBER_OF_ADJACENT_NODES = 8;
    while (AdjacentTileCounter <= NUMBER_OF_ADJACENT_NODES)
    {
        AdjacentTile = determineNeighboringTileNumber(SelectedTile, AdjacentTileCounter, aBoardObject);

        if (AdjacentTile >= 0)
            if ((aBoardObject.getIsCellOccupied(AdjacentTile) == false) && (aBoardObject.getColor(AdjacentTile) != RED))
            {
                if (isTileOnOpenList(AdjacentTile) == false)
                {
                    if (isTileOnClosedList(AdjacentTile) == false)
                    {
                        OpenList[OpenListIndex][TileIndexDimension] = AdjacentTile;
                        OpenList[OpenListIndex][ParentDimension] = SelectedTile;

                        GScore[AdjacentTile] = determineGScore(SelectedTile, AdjacentTileCounter);
                        HScore[AdjacentTile] = determineHScore(AdjacentTile, aBoardObject);
                        FScore[AdjacentTile] = GScore[AdjacentTile] + HScore[AdjacentTile];

                        myfile << "Adjacent #:  " << AdjacentTileCounter << "  Fscore:  " << FScore[AdjacentTile] << "  Gscore:  " << GScore[AdjacentTile] << "  Hscore:  " << HScore[AdjacentTile] << endl;

                        OpenListIndex++;        
                        NumberOfTilesOnOpenList++;

                        //to make sure we're not overwriting anything already on the list
                        while (OpenList[OpenListIndex][TileIndexDimension] != -1)
                        {
                            OpenListIndex++;
                    
                            if (OpenListIndex == NUMBER_OF_CELLS_ON_GRID)
                                OpenListIndex = 0;
                        }
                    }
                }

                //else if tile is on the open list, check the g score from this new path and see if it's lower.  if it is, this is a better route  
                else
                {
                    int TestGScore = determineGScore(AdjacentTile, AdjacentTileCounter);

                    if (TestGScore <= GScore[AdjacentTile])
                    {
                        OpenList[AdjacentTile][ParentDimension] = OpenList[SelectedTileIndex][TileIndexDimension];

                        GScore[AdjacentTile] = determineGScore(SelectedTile, AdjacentTileCounter);
                        HScore[AdjacentTile] = determineHScore(AdjacentTile, aBoardObject);
                        FScore[AdjacentTile] = GScore[AdjacentTile] + HScore[AdjacentTile];

                    }
                }
            }

        AdjacentTileCounter++;
    }

    myfile.close();
}

void Pathfinding::addSelectedTileToClosedList()
{
    //add to closed list
    ClosedList[ClosedListIndex][TileIndexDimension] = OpenList[SelectedTileIndex][TileIndexDimension];

    //save location on the closed list of the parent to the sqaure we just put on the closed list
    int counter = 0;
    while (counter < NumberOfTilesOnClosedList)
    {
        if (ClosedList[counter][TileIndexDimension] == OpenList[SelectedTileIndex][ParentDimension])
            ClosedList[ClosedListIndex][ParentDimension] = counter;
        
        counter++;
    }    

    ClosedListIndex++;
    NumberOfTilesOnClosedList++;
    
    //remove from open list
    OpenList[SelectedTileIndex][TileIndexDimension] = -1;
    OpenList[SelectedTileIndex][ParentDimension] = -1;
    NumberOfTilesOnOpenList--;
}

bool Pathfinding::determineIfGoalIsOnClosedList()
{
    int counter = 0;
    bool IsGoalOnClosedList = false;

    while (counter < NumberOfTilesOnClosedList)
    {
        if (ClosedList[counter][TileIndexDimension] == GoalLocation)
        {
            IsGoalOnClosedList = true;
            counter = 999999;
        }

        counter++;
    }

    if (IsGoalOnClosedList == false)
        return false;
    if (IsGoalOnClosedList == true)
        return true;

    return false;
}

void Pathfinding::resetVariablesToStartNewSearch()
{
    StartLocation = 0;
    GoalLocation = 0;

    OpenListIndex = 0;
    ClosedListIndex = 0;

    NumberOfTilesOnOpenList = 0;
    NumberOfTilesOnClosedList = 0;
    
    SelectedTile = 0;
    SelectedTileIndex = 0;

    int counter = 0;
    while (counter < NUMBER_OF_CELLS_ON_GRID)
    {
        OpenList[counter][0] = -1;
        ClosedList[counter][0] = -1;

        OpenList[counter][1] = -1;
        ClosedList[counter][1] = -1;

        FScore[NUMBER_OF_CELLS_ON_GRID] = -1;
        GScore[NUMBER_OF_CELLS_ON_GRID] = -1;
        HScore[NUMBER_OF_CELLS_ON_GRID] = -1;

        FinalPath[counter] = -1;

        counter++;
    }
    
}

int Pathfinding::determineFScore(int index, int ParentIsWhichNeighbor, Board aBoardObject)
{
    int Score = determineGScore(index, ParentIsWhichNeighbor) + determineHScore(index, aBoardObject);

    return Score;
}

int Pathfinding::determineGScore(int Parent, int ParentIsWhichNeighbor)
{
    int Score = 0;

    int ValueToAddToG = 0;

    //to determine whether this tile is diagonal or vertical/horizontal from its parent
    const int CellToTopLeft = 1;
    const int CellToTop = 2;
    const int CellToTopRight = 3;
    const int CellToLeft = 4;
    const int CellToRight = 5;
    const int CellToBottomLeft = 6;
    const int CellToBottom = 7;
    const int CellToBottomRight = 8;
    
    if (ParentIsWhichNeighbor == CellToTopLeft)
        ValueToAddToG = 14;
    if (ParentIsWhichNeighbor == CellToTopRight)
        ValueToAddToG = 14;
    if (ParentIsWhichNeighbor == CellToBottomLeft)
        ValueToAddToG = 14;
    if (ParentIsWhichNeighbor == CellToBottomRight)
        ValueToAddToG = 14;

    if (ParentIsWhichNeighbor == CellToTop)
        ValueToAddToG = 10;
    if (ParentIsWhichNeighbor == CellToLeft)
        ValueToAddToG = 10;
    if (ParentIsWhichNeighbor == CellToRight)
        ValueToAddToG = 10;
    if (ParentIsWhichNeighbor == CellToBottom)
        ValueToAddToG = 10;
        
    Score = (GScore[Parent] + ValueToAddToG);

    return Score;
}

int Pathfinding::determineHScore(int index, Board aBoardObject)
{
    int VerticalMovesCounter = 0;
    int HorizontalMovesCounter = 0;

    SDL_Rect CurrentLocation = aBoardObject.getCell(index);
    SDL_Rect EndCell = aBoardObject.getCell(GoalLocation);

    //get to the same height
    while (CurrentLocation.y != EndCell.y)
    {
        VerticalMovesCounter++;

        if (CurrentLocation.y < EndCell.y)
            CurrentLocation.y += SQUARE_HEIGHT;

        else if (CurrentLocation.y > EndCell.y)
            CurrentLocation.y -= SQUARE_HEIGHT;        
    }

    //get same x value
    while (CurrentLocation.x != EndCell.x)
    {
        HorizontalMovesCounter++;
        
        if (CurrentLocation.x < EndCell.x)
            CurrentLocation.x += SQUARE_WIDTH;

        else if (CurrentLocation.x > EndCell.x)
            CurrentLocation.x -= SQUARE_WIDTH;        
    }

    return ((VerticalMovesCounter + HorizontalMovesCounter) * 10);    
}


bool Pathfinding::isTileOnOpenList(int TileToCheck)
{
    int counter = 0;
    int index = 0;

    bool OnOpenList = false;

    while (counter < NumberOfTilesOnOpenList)
    {
        if (TileToCheck == OpenList[index][TileIndexDimension])
        {
            OnOpenList = true;
            counter = 9999;
        }
        
        if (OpenList[index][TileIndexDimension] != -1)
            counter++;

        index++;
    }

    if (OnOpenList == false)
        return false;
    if (OnOpenList == true)
        return true;

    return false;
}

bool Pathfinding::isTileOnClosedList(int TileToCheck)
{
    int counter = 0;
    int index = 0;

    while (counter < NumberOfTilesOnClosedList)
    {
        if (TileToCheck == ClosedList[index][TileIndexDimension])
            return true;
        
        if (ClosedList[index][TileIndexDimension] != -1)
            counter++;

        index++;
    }

    return false;
}


int Pathfinding::determineNeighboringTileNumber(int index, int WhichNeighbor, Board &aBoardObject)
{
    const int LastSquareOnxPlane = SCREEN_WIDTH - SQUARE_WIDTH;
    const int LastSquareOnyPlane = SCREEN_HEIGHT - SQUARE_HEIGHT;

    const int CellToLeft = index - 1;
    const int CellToRight = index + 1;
    
    const int CellToTop = index - NUMBER_OF_CELLS_HORIZONTAL;
    const int CellToBottom = index + NUMBER_OF_CELLS_HORIZONTAL;
    
    const int CellToBottomLeft = index + NUMBER_OF_CELLS_HORIZONTAL - 1;
    const int CellToBottomRight = index + NUMBER_OF_CELLS_HORIZONTAL + 1;

    const int CellToTopLeft = index - NUMBER_OF_CELLS_HORIZONTAL - 1;
    const int CellToTopRight = index - NUMBER_OF_CELLS_HORIZONTAL + 1;

    //top left 
    if (WhichNeighbor == 1)
        if (aBoardObject.getCell(index).x != 0)
            if (aBoardObject.getCell(index).y != 0)
                return CellToTopLeft;

    //top
    if (WhichNeighbor == 2)
        if (aBoardObject.getCell(index).y != 0)
            return CellToTop;

    //top right
    if (WhichNeighbor == 3)
        if (aBoardObject.getCell(index).x != LastSquareOnxPlane)
            if (aBoardObject.getCell(index).y != 0)
                return CellToTopRight;

        //left
    if (WhichNeighbor == 4)
        if (aBoardObject.getCell(index).x != 0)
            return CellToLeft;

    //right
    if (WhichNeighbor == 5)
        if (aBoardObject.getCell(index).x != LastSquareOnxPlane)
            return CellToRight;
    
    //bottom left
    if (WhichNeighbor == 6)
        if (aBoardObject.getCell(index).x != 0)
            if (aBoardObject.getCell(index).y != LastSquareOnyPlane)
                return CellToBottomLeft;

    //down
    if (WhichNeighbor == 7)
        if (aBoardObject.getCell(index).y != LastSquareOnyPlane)
            return CellToBottom;

    //bottom right
    if (WhichNeighbor == 8)
        if (aBoardObject.getCell(index).x != LastSquareOnxPlane)
            if (aBoardObject.getCell(index).y != LastSquareOnyPlane)
                return CellToBottomRight;
                

    return -2;
}

int Pathfinding::FindLowestFScoreOnOpenList()
{
    int LowestFScore = -1;
    int counter = 0, index = 0;

    while (counter < NumberOfTilesOnOpenList)
    {
        if (FScore[OpenList[index][TileIndexDimension]] != -1)
        {
            if (LowestFScore == -1)
            {
                LowestFScore = OpenList[index][TileIndexDimension];
                SelectedTileIndex = index;
            }

            else if (FScore[OpenList[index][TileIndexDimension]] <= FScore[LowestFScore])
            {
                LowestFScore = OpenList[index][TileIndexDimension];
                SelectedTileIndex = index;    
            }
            counter++;
        }

        index++;
    }

    return LowestFScore;
}

void Pathfinding::printBug()
{
    ofstream myfile;
    myfile.open ("bug.txt");
    myfile << "Start: " << StartLocation << endl;
    myfile << "End: " << GoalLocation << endl;
    myfile << "Selected: " << SelectedTile << endl;
    
    int counter = 0;
    while (counter < NUMBER_OF_CELLS_ON_GRID)
    {
        if (FinalPath[counter] != -1)
        {
            myfile << counter << ":  Path:  " << FinalPath[counter];
            myfile << endl;
        }
        counter++;
    }
    
    myfile << endl << endl ;
    counter = 0;
    while (counter < NUMBER_OF_CELLS_ON_GRID)
    {
        if (OpenList[counter][0] != -1)
        {
            myfile << counter << ":  OpenList:  " << OpenList[counter][0] << "  Parent  "  << OpenList[counter][1];
            myfile << endl;
        }

        counter++;
    }
    myfile << endl << endl;
    counter = 0;
    while (counter < NUMBER_OF_CELLS_ON_GRID)
    {
        if (ClosedList[counter][0] != -1)
        {
            myfile << counter << ":  ClosedList:  " << ClosedList[counter][0] << " Parent:  " << ClosedList[counter][1];
            myfile << endl;
        }

        counter++;
    }

    myfile << endl << endl;
    counter = 0;
    while (counter < NUMBER_OF_CELLS_ON_GRID)
    {
        if (FScore[counter] != -1)
        {
            myfile << counter << ":  FScore:  " << FScore[counter] << ":  GScore:  " << GScore[counter] << ":  HScore:  " << HScore[counter];
            myfile << endl;
        }

        counter++;
    }

    myfile.close();
}

int Pathfinding::getFinalPath(int index)
{
    return FinalPath[index];
}

Now I have to get this working on a hex board instead of a sqaure grid

 

[sub]

Aaaaaaaaaaaaaaaaaaaaaaaaaaannnnnnd I have it working on a hex map now. The, uh, boats are the path.

 

[sub]

I really have no idea what I'm doing. I started to implement the AI in a way that I thought probably made sense, and I wanted it to check each city location and determine which was the closest city to a given unit. There are 20 cities on the map, so this means 20 times you need to find a path. I must have ****ed that pathfinding algorithm up somehow, because the program would hang for roughly 90 years before finishing that. It was instant to find one path, but I guess god forbid you give it a few in a row. The pathfinding wasn't using any heuristics (guessing which is the most likely route. wasn't sure how to calculate the heuristic score for hexes), but I think it should have still been faster than it was.

**** it, I thought. I'll make a new pathfinding class, one that stores the path to every possible location you can travel to from any given hex. Then I can have it create poetry or do whatever the **** I want inbetween turns and it won't lag. The concept I used was much easier to understand, and it took the game less than a second for it to generate every ******* possible path for a given map. The other pathfinding attempt I made couldn't even do 20 in a row, this did 220 * 220 in no time and you only need it to find paths once per map.

I made a pretty picture to illustrate how it works
edit: I ****ed the numbering up a bit, actually, but pretend it's all right.

So say you have a unit in the purple hex with the star in the middle. There's a two dimensional array that stores the starting hex in the first dimension, and in the second dimension, a number to represent how many turns it takes to get to that hex from the starting hex. If you want to find a path, you start at the end, look at every adjacent hex and pick the lowest tile number. Keep repeating that and then you'll get to the starting point with the shortest path.

And since I posted the code for the other one, I'll do it for this one too. I still need to do something about adding in a penalty for water movement, but other than that it works.

Pathfinding.h

#ifndef PATHFINDING_H
#define PATHFINDING_H

#include "constants.h"

class Board;

//Brief explanation for how this works 
//The array MovementPaths actually contains the shortest path from any given hex to any other given hex on the map
//The first dimension represents each hex tile on the map, since in the board class every hex is just part of the same one dimensional array anyway
//The second dimension contains a number to represent how many turns it takes to reach that hex from the starting hex
//If you want to find a path, you would start at the end and look at all adjacent hexes and pick the lowest number.
//Keep doing this until you reach your goal, and you now have the shortest path.
//When The player picks a nation the map is analyzed and these routes created

class Pathfinding 
{
private:
    int MovementPaths[NUMBER_OF_HEXES_ON_MAP][NUMBER_OF_HEXES_ON_MAP];

    //for initializing movement paths
    int TilesInQueue[NUMBER_OF_HEXES_ON_MAP];

    int StartLocation, EndLocation;
    int StartTileIndex, GoalTileIndex;

    int NumberOfTilesAddedToEndTileDimension;

    int NumberOfTilesInQueue;

    int CurrentScore;

public:
    Pathfinding();

    int findNextTileToMoveTo(int start, int goal, Board &aBoardObject);
    
    void initializeMovementPaths(Board aBoardObject);

    bool isTileAlreadyRanked(int index);
    bool isTileAlreadyInQueue(int index);

    void saveAllTilesInQueue();
    void getNewTilesForQueue(Board aBoardObject);
    void removeRankedTilesFromQueue();

    void manageStartTileIndexAndGoalTileIndex();

    void resetAllVariables();

    void printBug();
};

#endif

Pathfinding.cpp

#include "pathfinding.h"
#include "board.h"

#include <iostream>
#include <fstream>

using namespace std;

Pathfinding::Pathfinding()
{
    int counter = 0, counter2 = 0;
    while (counter2 < NUMBER_OF_HEXES_ON_MAP)
    {
        MovementPaths[counter][counter2] = -1;

        counter++;
        if (counter == NUMBER_OF_HEXES_ON_MAP)
        {
            counter = 0;
            counter2++;
        }
    }

    counter = 0;
    while (counter < NUMBER_OF_HEXES_ON_MAP)
    {
        TilesInQueue[counter] = -1;
        counter++;
    }

    StartLocation = -1;
    EndLocation = -1;
    
    StartTileIndex = 0;
    GoalTileIndex = 0;

    CurrentScore = 0;

    NumberOfTilesInQueue = 0;

    NumberOfTilesAddedToEndTileDimension = 0;
}

//returns the next tile a unit at the start location should move to in order to reach the goal
int Pathfinding::findNextTileToMoveTo(int start, int goal, Board &aBoardObject)
{
    return -1;
}
    
void Pathfinding::resetAllVariables()
{
    int counter = 0, counter2 = 0;
    while (counter2 < NUMBER_OF_HEXES_ON_MAP)
    {
        MovementPaths[counter][counter2] = -1;

        counter++;
        if (counter == NUMBER_OF_HEXES_ON_MAP)
        {
            counter = 0;
            counter2++;
        }
    }

    StartLocation = -1;
    EndLocation = -1;

    counter = 0;
    while (counter < NUMBER_OF_HEXES_ON_MAP)
    {
        TilesInQueue[counter] = -1;
        counter++;
    }

    StartTileIndex = 0;
    GoalTileIndex = 0;

    CurrentScore = 0;

    NumberOfTilesInQueue = 0;

    NumberOfTilesAddedToEndTileDimension = 0;
}

void Pathfinding::initializeMovementPaths(Board aBoardObject)
{
    resetAllVariables()
    
    while (StartTileIndex < NUMBER_OF_HEXES_ON_MAP)
    {
        saveAllTilesInQueue();

        getNewTilesForQueue(aBoardObject);

        removeRankedTilesFromQueue();

        manageStartTileIndexAndGoalTileIndex();

        counter++;
    }
    printBug();
    //aBoardObject.setTileType(0, PORT);
}

void Pathfinding::saveAllTilesInQueue()
{
    int counter = 0;
    while ((counter < NumberOfTilesInQueue) && (NumberOfTilesInQueue != 0))
    {
        MovementPaths[StartTileIndex][TilesInQueue[counter]] = CurrentScore;

        NumberOfTilesAddedToEndTileDimension++;
        
        counter++;
    }

    CurrentScore++;
}

void Pathfinding::getNewTilesForQueue(Board aBoardObject)
{
    //if we're at the start of a new cycle, add starting tile to the queue and iterate the NumberOfTilesInQueue by one, then save 
    if (NumberOfTilesInQueue == 0)
    {    
        //save the starting tile as the first element of the array
        CurrentScore = 0;
        TilesInQueue[0] = StartTileIndex;
        NumberOfTilesInQueue++;

        saveAllTilesInQueue();
    }

    //add all adjacent tiles to the list to be ranked if they aren't already ranked.  If they are ranked, ignore them
    int TilesInQueueCounter = 0;
    int IndexForAddingNewTilesToList = NumberOfTilesInQueue;

    while (TilesInQueueCounter < NumberOfTilesInQueue)
    {
        int AdjacentTileCounter = 1;
        int AdjacentTile = -1;

        const int NUMBER_OF_ADJACENT_TILES = 6;
        while (AdjacentTileCounter <= NUMBER_OF_ADJACENT_TILES)
        {
            AdjacentTile = aBoardObject.determineNeighborHexNumber(TilesInQueue[TilesInQueueCounter], AdjacentTileCounter);

            if (AdjacentTile >= 0)
            {
                //if ((aBoardObject.getTileType(AdjacentTile) != WATER))
                {
                    if (isTileAlreadyInQueue(AdjacentTile) == false)
                    {
                        if (isTileAlreadyRanked(AdjacentTile) == false)
                        {
                            TilesInQueue[IndexForAddingNewTilesToList] = AdjacentTile;
                            IndexForAddingNewTilesToList++;
                            //we don't change NumberOfTilesInQueue here, that's done in removeRankedTilesFromQueue
                        }
                        else //if tile is already ranked, check to see if this tile is better.  if so, replace that one with this one
                            if (MovementPaths[StartTileIndex][AdjacentTile] > CurrentScore)
                                MovementPaths[StartTileIndex][AdjacentTile] = CurrentScore;
                    }
                }
                //else //if tile is water consider it as being added since we ignore water
                //{
                    //NumberOfTilesAddedToEndTileDimension++;
                    
            //    }
            }

            AdjacentTileCounter++;
        }
        TilesInQueueCounter++;
    }
}

bool Pathfinding::isTileAlreadyRanked(int index)
{
    if (MovementPaths[StartTileIndex][index] != -1)
        return true;

    if (MovementPaths[StartTileIndex][index] == -1)
        return false;

    return 0;
}

bool Pathfinding::isTileAlreadyInQueue(int index)
{
    int counter = 0;
    bool IsTileInQueue = false;
    while (TilesInQueue[counter] != -1)
    {
        if (TilesInQueue[counter] == index)
            IsTileInQueue = true;
        counter++;
    }

    if (IsTileInQueue == true)
        return true;

    if (IsTileInQueue == false)
        return false;

    return 0;
}

void Pathfinding::removeRankedTilesFromQueue()
{
    //this function removes every tile we have saved on the queue and then moves the tiles that aren't saved to the front of the queue

    //remove the elements already ranked from the queue
    int counter = 0;
    while (counter < NumberOfTilesInQueue)
    {
        TilesInQueue[counter] = -1;
        counter++;
    }
    
    //move up everything to the front of the queue
    counter = NumberOfTilesInQueue;
    int i = 0;
    int NewNumberOfUnitsInQueue = 0;
    int CounterForNextLoop = 0;
    while (TilesInQueue[counter] != -1)
    {
        TilesInQueue[i] = TilesInQueue[counter];
        TilesInQueue[counter] = -1;
        
        NewNumberOfUnitsInQueue++;
        i++;
        counter++;
    }
    //printBug();

    NumberOfTilesInQueue = NewNumberOfUnitsInQueue;
}

void Pathfinding::manageStartTileIndexAndGoalTileIndex()
{
    //if we've analyzed every path on the map for this starting tile, increment that by 1
    if (NumberOfTilesAddedToEndTileDimension == NUMBER_OF_HEXES_ON_MAP)
    {
        StartTileIndex++;
        NumberOfTilesInQueue = 0;
        NumberOfTilesAddedToEndTileDimension = 0;

        /*
        //i don't think this is necessary
        int counter = 0;
        while (counter < NUMBER_OF_HEXES_ON_MAP)
        {
            TilesInQueue[counter] = -1;
            counter++;
        }*/
    }    
}

void Pathfinding::printBug()
{
    ofstream myfile;
    myfile.open ("bug.txt");
    
    /*
    int counter = 0;
    while (counter < NUMBER_OF_HEXES_ON_MAP)
    {
        myfile << counter << ":  Queue:  " << TilesInQueue[counter] << endl;
        counter++;
    }
    myfile << endl << endl << endl;
    */
    StartTileIndex = 0;
    GoalTileIndex = 0;
    int counter = 0;
    while (StartTileIndex < NUMBER_OF_HEXES_ON_MAP)
    {
        //if (MovementPaths[StartTileIndex][counter] != -1)
        myfile << GoalTileIndex << ":  StartingTile:  " << StartTileIndex << "  MovementPathsHolder:  "  << MovementPaths[StartTileIndex][GoalTileIndex] << endl;
        GoalTileIndex++;
        if (GoalTileIndex == 220)
        {
            GoalTileIndex = 0;
            StartTileIndex++;
            myfile << endl << endl << endl;
            myfile << endl << endl << endl;
            myfile << endl << endl << endl;
            myfile << endl << endl << endl;
            myfile << endl << endl << endl;
        }
    }






    /*    
    myfile << endl << endl ;
    counter = 0;
    while (counter < NUMBER_OF_HEXES_ON_MAP)
    {
        if (OpenList[counter][0] != -1)
        {
            myfile << counter << ":  OpenList:  " << OpenList[counter][0] << "  Parent  "  << OpenList[counter][1];
            myfile << endl;
        }

        counter++;
    }
    myfile << endl << endl;
    counter = 0;
    while (counter < NUMBER_OF_HEXES_ON_MAP)
    {
        if (ClosedList[counter][0] != -1)
        {
            myfile << counter << ":  ClosedList:  " << ClosedList[counter][0] << " Parent:  " << ClosedList[counter][1];
            myfile << endl;
        }

        counter++;
    }

    myfile << endl << endl;
    counter = 0;
    while (counter < NUMBER_OF_HEXES_ON_MAP)
    {
        if (FScore[counter] != -1)
        {
            myfile << counter << ":  FScore:  " << FScore[counter] << ":  GScore:  " << GScore[counter] << ":  HScore:  " << HScore[counter];
            myfile << endl;
        }

        counter++;
    }
    */
    myfile.close();
}

 

[sub]

Yeah, I'm trying to debug this right now. It works 99% of the time, but 1% of the time it will **** up and start a path from the wrong place. I really have no idea why. If I no longer make any posts after this, it's because I've killed myself from frustration.

 

[Shadi]

Yeah, I'm trying to debug this right now. It works 99% of the time, but 1% of the time it will **** up and start a path from the wrong place. I really have no idea why. If I no longer make any posts after this, it's because I've killed myself from frustration.

Now little Sub, it's alright.. you'll finish it someday.

 

[sg2]

Now little Sub, it's alright.. you'll finish it someday.

Shadi, get back to your room.
And clean up your bed it's smelling of alien soup!

 

[sub]

I'm convinced my program is haunted. The pathfinding assigns some tiles the wrong values and I'm not sure why. I made it print the number of turns it takes to reach a tile from a starting tile chosen at random so I could see just where it's making a mistake and try to find a pattern. Not all maps produce a mistake, but here's two examples of it ******* up

If I can figure this out, I'll be very happy.

 

[sub]

I guess I'm very happy. I have absolutely no idea why the old code was ******* up and giving me a hard time, but I've fixed it by changing the way scores are given out to tiles. Now I temporarily save the parent tile of hexes and then assign new hexes to be the parent value + 1. That's what the old code should have done, but I rewrote it to do that more implicitly. I suppose there was some obscure case where the old code wasn't doing that, but now it kind of has no choice.

I must have generated 100 different maps and checked the assigned values to make sure it's working, and so far it's worked without a hitch. I think it's finally done unless I've missed something.

Now onto the AI

 

[Shadi]

Gj Dan, I knew it'd be done at some point... you fought well!

 

[sg2]

It is amazing how things that are so seemingly simple are, in actuality, entirely complex and on a whole different resolution from what we had originally thought...

"Just" a hex game, and yet it has so much depth in its background mechanics.
You're a true artist, Sub!

Not alike Shadi on draw-something-free, with his abomination mutant excuses for "drawings". He draws with toes.

 

[sub]

I feel like I should warn you all that it's alive. Right now the AI will move its units to grab any city owned by no one, starting with the cities closest to it. AI is actually fun to do.

And yeah, I agree sg2. Shadi sucks and I'm pretty awesome.

 

[Shadi]

It is amazing how things that are so seemingly simple are, in actuality, entirely complex and on a whole different resolution from what we had originally thought...

"Just" a hex game, and yet it has so much depth in its background mechanics.
You're a true artist, Sub!

Not alike Shadi on draw-something-free, with his abomination mutant excuses for "drawings". He draws with toes.

You guessed my awesome chair :/

Also I agree with Sub's words towards you. I don't suck though!! You can't tell that to your son, Sub!

 

[sub]

So I'm unbanned now, which is nice. A few things:

I want to finish my turn based strategy game that I was doing, but I can't seem to get the AI to work properly, so I'm going to take a bit of a break from that.

I'm going to make a very very quick clone of the game drug wars, and I'm going to learn a GUI library while doing so. Probably QT. I want to finish this one in like a day or two...

I learned Python! I like c++ better, but Python is pretty cool.

It always bothered me that the random number generator in the Tetris game I made sucked, so I went back and spent an hour on fixing it. Implemented a third party library that generated random numbers, but still wasn't entirely happy. Some implementations of Tetris ensure that you always get an even distribution of shapes, which is what I opted to do try after that. To do that, there are 7 shapes in the game, so you could create an array of size 21 to store each shape three times. Then you could randomly draw and remove a number from this array. You'd refill it when you run out of numbers. This would ensure that you'd get a random number, but you wouldn't get 26 S pieces in a row, which might happen with a completely random approach. I also fixed a small bug with shape rotation.

Tetris Download Link
Also made a video of the game really quick
http://www.youtube.com/watch?v=Te00Z9AeSCY&list=PL664F3414E5A4ECB2&feature=mh_lolz

I also started to plan out the game I want to work on after I make that drug wars clone. It's going to pretty much be the best thing ever. Wrote a detailed post on what I want that game to be here. http://forum.esforces.com/threads/1...a-space-game?p=1951823&viewfull=1#post1951823

 

[Deathshot]

Welcome back, Sub! I am waiting for another Text Adventure from you.

 

[Baaja]

That's inspiring Sub! Keep up the good work!

 

[dutchmeat]

Ratatat - Loud pipes, always +1

 

[sub]

Thank you for the kind words guys.

Anyways, this is not that hard to do, but I spent a little time on this 2d water program

http://www.youtube.com/watch?v=InUoSQdHdf0

Link

I might make it better, but this was just a quick project. On a side note, since it's on the current version of SDL, it's using all CPU and no graphics card, so it's pretty slow. I had the water a bit transparent, with it being darker towards the bottom, but that made it a bit laggy so I took it out. I think I'm going to switch over to using SFML from now on, since that has a bit more functionality, is C++ based instead of C, and it's accelerated hardware.

edit: Also, I wasn't going to, but I'm going to make another text adventure.

 

[sg2]

Neat! I'll be your beta-tester if you so desire.