Humble Bundle V on Debian Wheezy 64bit

Tags

, , , ,

I just bought the Humble Bundle V and, all happily, i tried to install some games from it. First i downloaded Swords&Sworcery and the installed without any problems. Next i wanted to install Bastion.
I’ve downloaded the installer script, ran it as user. First thing, i seem not to have enough space in /tmp (found out that debian uses RAM for tmp, and only 1G), changed that to some folder in home. Choose /usr/shared/games as install folder, /usr/bin as binaries folder, enter root password, and there it stopped.
So, no problem i thought, run the script as root. I did. It installed the game in /usr/shared/games, but no uninstall script in /usr/bin, and only root has permission to run it. Now, that’s not acceptable.
Third try, found that i’m not the only one that has some problems with this, Urfoex explains how he installed it. Tried that as user, with same result as first run. So i decided i’ll do it manually. (Anything you see here and decide to run on your computer, you do so at your own risk, double check everything for typos and don’t blame me if something dies in the process)

$ ./Bastion-HIB-2012-06-01-1.sh --target ~/BastionExtract --noexec --keep
$ cd ~/BastionExtract/
$ ./startupinstaller.sh

Choose ~/Binaries as install folder, choose ~/bin as binaries folder, and install. That went well, and worked, and had uninstall script in ~/bin. But i still wanted it in /usr/bin and /usr/share/games where it belongs.
So, a few steps for that (this is done as root, every instance of “user” should be replaced with your username, now and everywhere in this post):
# chown -R root:root /home/user/Binaries/Bastion
# chmod -R a+r /home/user/Binaries/Bastion
# mv /home/user/Binaries/Bastion /usr/share/games/

Next, open ~/.local/share/applications/Bastion.desktop and edit the folowing lines to:
Exec=/usr/share/games/Bastion/Bastion.bin.x86_64
Icon=/usr/share/games/Bastion/Bastion.png

Now that’s great, but when you try to run it, permission denied. Only the root can run it now. So change the permission of binary to allow anyone to run it.
# chmod a+x /usr/share/games/Bastion/Bastion.bin.x86_64

Try to run it, permission denied again. Right, there is a few more files that need execute permission in order to run the game. At this point i could either manually try to change permission of unknown number of files in Bastions install folder, or do it somehow automagicaly. Since i’m not nearly good enough with bash to search and change permissions only using grep and pipes, i decided to write a python script to do it for me. Basically what this does is checks if file (or folder) has execute permission, and if it does grants execute for everyone (script checks whether there is Bastion executable in chosen folder before it does anything, but since you have to run it as root, standard care is advised):
#! /usr/bin/python
# -*- coding: utf-8 -*-

from subprocess import call
import os, sys
from stat import *

def walktree(top, callback):
    '''recursively descend the directory tree rooted at top,
       calling the callback function for file and directory
       that has execute permission by owner'''

    for f in os.listdir(top):
        pathname = os.path.join(top, f)
        mode = os.stat(pathname).st_mode
        if S_ISDIR(mode):
            if S_IXUSR & os.stat(pathname)[ST_MODE]:
                callback(pathname)
            walktree(pathname, callback)
        elif S_ISREG(mode):
            if S_IXUSR & os.stat(pathname)[ST_MODE]:
                callback(pathname)
        else:
            # Unknown file type, print a message
            print 'Skipping %s' % pathname

def visitfile(path):
    print 'Executable by owner:', path
    
def grant_permission(path):
    call(["chmod", "a+x" , path])

if __name__ == '__main__':
    path = sys.argv[1]
    if os.path.isfile(''.join([path, 'Bastion.bin.x86_64'])):
        walktree(path, grant_permission)
    else:
        print('This doesn\'t seem to be Bastion install folder.')

Save it somewhere as something.py, say grant_perm.py. Grant it execute permission with:
# chmod +x grant_perm.py

And run it with (assuming you have put the install folder where I have):
# ./grant_perm /usr/share/games/Bastion/

Again, this is ran as root, you should be aware of what code does before you run anything from internet, be it as user or root.
If you try to run Bastion now, it should work for any user (you might need to copy/modify Bastion.desktop to other users home folders).
Only thing left to do is to fix uninstall script. Open ~/bin/uninstall-Bastion in gedit (or whichever text editor you prefer). Find and replace “/home/user/Binaries” with “/usr/share/games”. Find and replace “/home/user/bin” with “/usr/bin”. REMOVE SECOND TO LAST LINE IN uninstall-Bastion. This line will try to remove your /usr/bin folder, it should fail since it uses rmdir, but i still don’t like it.
After this is done, change owner to root and move uninstall script to /usr/bin:
# chown root:root /home/user/bin/uninstall-Bastion
# mv /home/user/bin/uninstall-Bastion /usr/bin/

You can now remove /home/user/bin/ folder if you don’t use it:
$ rmdir /home/user/bin

That’s it. It should now work for anyone and be removable only by root.

A different kind of game

I have known about Conway’s Game of Life for a long time, but have never implemented it. If you aren’t familiar, game of life is a cellular automaton, where each cells life/death is determined by number of it’s neighbors as follows:

- a living cell with less than two neighbors dies

- a living cell with two or three neighbors lives

- a living cell with more than three neighbors dies

- a dead cell with exactly three neighbors becomes alive

Since i have been playing with SDL recently, i thought: “Why not, that shouldn’t be a problem”. So a few hours later, i got a working (but rather slow) implementation.

The SDL part is based on this tutorial, which i have been using for another project, so i was familiar with it. There is no control one the simulation is running, but it’s possible to define number of cells, percentage of initial live cells, and time to live of each generation.

Screenshot:

Screenshot-Game of Lifeit’s simple, yet somehow quite mesmerizing… oh, and here is the source, with Qt Creator project as usual…

GNOME 3 extensions

Tags

, , ,

Debian recently upgraded its testing version from GNOME 2 to GNOME 3. I don’t think it’s great, and i don’t think it’s worst thing in universe. I do however find it to lack some things, one of them being weather extension.

Searching a little on internet, i ended up at fpmurphys blog. He made some great extensions for GNOME 3, as well as a few great posts about how GNOME 3 works. Among them was weather extension which i downloaded. While the extension worked, there were a few problems. First one was that he implemented only support for US zip codes, which doesn’t help me a lot. Then, he replaced °F with °C in at least one place, and  he didn’t have “°C” or “°F” next to temperatures. Also, he rendered it in center of screen, where i don’t like to have anything that i’m not working with currently.

I played a bit around with that extension and fixed the issues and implemented support for world weather. To install weather extension, extract it into ~/.local/share/gnome-shell/extensions/. You’ll have to configure thins extension, read the included README for all details. When you are done with configuring, hit Alt+F2, type ‘r’ and hit enter to restart gnome-shell. If there is a problem, try Alt+F2, ‘lg’ to open looking glass.

Here’s am image of extension in action:GNOME 3 weather extension

Second thing that really disliked about GNOME 3 was that awful “Activities” text in upper left corner. First, it reminds me of “Start” button of windows, second, i feel like they couldn’t come up with an icon so they just left “Activities” text instead. And again, fpmurphy had a solution for that  as well. A simple extension, one icon from debians logo page, and here we are:

GNOME3 Activities textDebian Activities icon

Just extract to ~/.local/share/gnome-shell/extensions/, copy included icon to ~/.local/share/icons/ and restart gnome shell.

If you are stuck, please read the included README files.

Running A*

Tags

,

And this is how it looks when ran on romania with explain enabled:

Frontier: Arad,  
Arad path cost: 0 transition + 366 estimated =          366 
Best path: Arad, with cost of: 366 
 
Frontier: Zerind, Sibiu, Timisara,  
Zerind path cost: 75 transition + 374 estimated =          449 
>>   Sibiu path cost: 140 transition + 253 estimated =         393 
>>   Timisara path cost: 118 transition + 329 estimated =         447 
Best path: Sibiu, with cost of: 393 
 
Frontier: Zerind, Timisara, Oradea, Rimnicu Vilcea, Fargaras,  
Zerind path cost: 75 transition + 374 estimated =          449 
>>   Timisara path cost: 118 transition + 329 estimated =         447 
>>   Oradea path cost: 291 transition + 380 estimated =         671 
>>   Rimnicu Vilcea path cost: 220 transition + 193 estimated =         413 
>>   Fargaras path cost: 239 transition + 176 estimated =         415 
Best path: Rimnicu Vilcea, with cost of: 413 
 
Frontier: Zerind, Timisara, Oradea, Fargaras, Pietisti, Craiova,  
Zerind path cost: 75 transition + 374 estimated =          449 
>>   Timisara path cost: 118 transition + 329 estimated =         447 
>>   Oradea path cost: 291 transition + 380 estimated =         671 
>>   Fargaras path cost: 239 transition + 176 estimated =         415 
>>   Pietisti path cost: 317 transition + 100 estimated =         417 
>>   Craiova path cost: 366 transition + 160 estimated =         526 
Best path: Fargaras, with cost of: 415 
 
Frontier: Zerind, Timisara, Oradea, Pietisti, Craiova, Bucharest,  
Zerind path cost: 75 transition + 374 estimated =          449 
>>   Timisara path cost: 118 transition + 329 estimated =         447 
>>   Oradea path cost: 291 transition + 380 estimated =         671 
>>   Pietisti path cost: 317 transition + 100 estimated =         417 
>>   Craiova path cost: 366 transition + 160 estimated =         526 
>>   Bucharest path cost: 450 transition + 0 estimated =         450 
Best path: Pietisti, with cost of: 417 
 
Frontier: Zerind, Timisara, Oradea, Craiova, Bucharest, Craiova, Bucharest,  
Zerind path cost: 75 transition + 374 estimated =          449 
>>   Timisara path cost: 118 transition + 329 estimated =         447 
>>   Oradea path cost: 291 transition + 380 estimated =         671 
>>   Craiova path cost: 366 transition + 160 estimated =         526 
>>   Bucharest path cost: 450 transition + 0 estimated =         450 
>>   Craiova path cost: 455 transition + 160 estimated =         615 
>>   Bucharest path cost: 418 transition + 0 estimated =         418 
Best path: Bucharest, with cost of: 418 
 
Route:  
Arad -> Sibiu -> Rimnicu Vilcea -> Pietisti -> Bucharest 
 
************************   GOAL REACHED!   ************************************ 
Number of steps: 5 

Main

Tags

,

This are the two files that were missing to compile and run this. First is definitions.h. In that file it’s defined whether solving of maze or regular problem is desired, and if program should explain what it’s doing.

It’s preset to run romania and explain what and why it’s doing it.

The next one is main.cpp. As you can see i’m running this in QtCreator, so there is a few lines you should probably remove if you don’t.

There si nothing special here, we create Romania from thin air and loop through it step by step until solution is found, there is no solution, or there is no more steps to take.

Runtime is calculated, and so are steps. But on example of romania both are insignificant.

And there it is, a A* implementation ready to solve any problem you are patient enough to hardcode into it, or write a generator for.

definitions.h

#ifndef DEFINITIONS_H
#define DEFINITIONS_H

#define EXPLAIN

#define SOLVE_ROMANIA

//#define SOLVE_MAZE

#ifdef SOLVE_MAZE
#define X_SIZE 10
#define Y_SIZE 5
#define COVERAGE 0.10
#endif

#endif // DEFINITIONS_H

main.cpp

#include <QtCore/QCoreApplication>
#include <iostream>
#include "maze.h"
#include "state.h"
#include "astar.h"
#include <time.h>
#include "romania.h"
#include "definitions.h"

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    clock_t start=0,end=0;
#ifdef SOLVE_MAZE
    Maze* maze = new Maze(X_SIZE, Y_SIZE, COVERAGE);
    maze->printMaze();
    AStar AS(maze);
#endif
#ifdef SOLVE_ROMANIA
    Romania* romania = new Romania();
    AStar AS(romania->StartState);
#endif
    start = clock();
    for (int i = 0; i < 100000; ++i) {
        if (AS.makeStep()) {
            std::cout << "Number of steps: " << i << std::endl;
            end = clock();
            std::cout << "Time to solve: " << (double)(end-start) / (double)CLOCKS_PER_SEC << " seconds" << std::endl;
            break;
        }
    }
    return a.exec();
}

Romania

Tags

,

This is just representation of a problem introduced at Stafords online AI class, just represented as a bunch of states and transitions friendly to this implementation.

There is pointer to start and goal state, a constructor in which the whole structure is made and a helping method which for given vector<State*> and index of origin and destination in that vector makes transitions between those two states.

The only thing left is write a main() function and test it.

romania.h

#ifndef ROMANIA_H
#define ROMANIA_H

#include "state.h"
#include "transition.h"
#include <vector>

class Romania
{
private:
    void addTransition(std::vector<State*> sl, int f, int t, int c = 1);  // add transitions sl[f]<=>sl[t] of cost c
public:
    State* StartState;  // pointer to first state in maze
    State* GoalState;   // pointer to goal state in maze
    Romania();
};

#endif // ROMANIA_H

romania.cpp

#include "romania.h"

Romania::Romania()
{
    std::vector<State*> States;  // create list to hold pointers to all the states in maze while we are creating it
    States.push_back(new State(false,false, "Arad", 366));
    States.push_back(new State(false,false, "Zerind", 374));
    States.push_back(new State(false,false, "Oradea", 380));
    States.push_back(new State(false,false, "Timisara", 329));
    States.push_back(new State(false,false, "Lugoj", 244));
    States.push_back(new State(false,false, "Drobeta", 242));
    States.push_back(new State(false,false, "Mehadia", 241));
    States.push_back(new State(false,false, "Sibiu", 253));
    States.push_back(new State(false,false, "Rimnicu Vilcea", 193));
    States.push_back(new State(false,false, "Craiova", 160));
    States.push_back(new State(false,false, "Pietisti", 100));
    States.push_back(new State(false,false, "Fargaras", 176));
    States.push_back(new State(true,false, "Bucharest", 0));
    States.push_back(new State(false,false, "Giurgu", 77));
    States.push_back(new State(false,false, "Urziceni", 80));
    States.push_back(new State(false,false, "Hirsova", 151));
    States.push_back(new State(false,false, "Efric", 161));
    States.push_back(new State(false,false, "Vasuli", 199));
    States.push_back(new State(false,false, "Iasi", 226));
    States.push_back(new State(false,false, "Neamt", 234));
    StartState = States[0];
    GoalState = States[12];
    addTransition(States, 0, 1, 75);
    addTransition(States, 0, 7, 140);
    addTransition(States, 0, 3, 118);
    addTransition(States, 1, 2, 71);
    addTransition(States, 2, 7, 151);
    addTransition(States, 3, 4, 111);
    addTransition(States, 4, 6, 70);
    addTransition(States, 6, 5, 75);
    addTransition(States, 5, 9, 120);
    addTransition(States, 7, 8, 80);
    addTransition(States, 7, 11, 99);
    addTransition(States, 8, 10, 97);
    addTransition(States, 8, 9, 146);
    addTransition(States, 9, 10, 138);
    addTransition(States, 10, 12, 101);
    addTransition(States, 11, 12, 211);
    addTransition(States, 12, 13, 90);
    addTransition(States, 12, 14, 85);
    addTransition(States, 14, 15, 98);
    addTransition(States, 15, 16, 86);
    addTransition(States, 14, 17, 142);
    addTransition(States, 17, 18, 92);
    addTransition(States, 18, 19, 87);


}

void Romania::addTransition(std::vector<State*> sl, int f, int t, int c) {  // add transitions sl[f]<=>sl[t] of cost c
    sl[f]->Transitions.push_back(new Transition(sl[f], sl[t], c));  // add to current states transitions
    sl[t]->Transitions.push_back(new Transition(sl[t], sl[f], c));  // add to next states transitions
}

A*

Tags

,

So, here is the neat part of it. The implementation at last. I mentioned that this started from xkcd irc. So there was talk about finding path from start S to goal G, in rectangular field, filled with impassable obstacles at random places. So Maze* maze is just a pointer to a class that stores such structure (actually, class stores generator and some data and methods to display maze and result, maze is stored in memory same as any other problem).

Next, there is vector<Path*> Frontier, in which pointers to last state in each path is stored. There are two constructors, one is general, creating object from a State (start state), other is for creating it from above mentioned maze.

And finally there is what makes it all tick, the makeStep() method.

So how does it all works? First, when constructing the object, a Path is created, start State is added to that path. After that, the path is added to Frontier.

Then, object is ready to solve the problem.

First thing, A* must find best path in frontier [to clarify, in frontier are stored unopened paths]. A* does that by calculating cost of each path f(p), as sum of g(p) and h(p), where g(h) is cost of path to state p, and h(p) is expected cost from state p to goal. So its assumed that first path is best and then checked if that really is case.

Once the best path is known, last state of that path it’ looked at, checked if it is the goal state. In case it success is declared, best path is printed and 1 is returned to acknowledge success. Most of the time that won’t be the case, so the path is removed from frontier, a vector of paths is created to store all possible unexplored paths from current state. After that a copy of current path for every new path is created. And then, the newly reachable places are added, one to end of each path. Cost of each new path is increased, and paths are added to frontier.

Finally, it’s checked if there are any paths in frontier, if not, it means that there is no path from start to goal, and thus a defeat is announced and last path is printed.

And that’s all there is to it.

astar.h

#ifndef ASTAR_H
#define ASTAR_H

#include <iostream>
#include <vector>
#include "path.h"
#include "maze.h"
#include "romania.h"
#include "definitions.h"

class State;
class Transition;

class AStar
{
private:
    Maze* maze;  // pointer to maze we are solving
    std::vector<Path*> Frontier;  // list of pointers to paths in frontier
public:
    AStar(State* s);
    AStar(Maze* m);  // construct from maze
    int makeStep();  // make one step in maze
};

#endif // ASTAR_H

astar.cpp

#include "astar.h"

AStar::AStar(Maze* m) {
    maze = m;
    Path* WorkingPath = new Path(maze->StartState);
    Frontier.reserve(sqrt(maze->X()*maze->Y()));
    Frontier.push_back(WorkingPath);
}

AStar::AStar(State* s) {
    Path* WorkingPath = new Path(s);
    Frontier.push_back(WorkingPath);

}

int AStar::makeStep() {
#ifdef EXPLAIN
    std::cout << std::endl << "Frontier: ";
    for (int i = 0; i < Frontier.size(); ++i) {
        std::cout << Frontier[i]->LastState()->Name() << ", ";
    }
    std::cout << std::endl;
#endif
    int BestPath = 0;
    int BestPathCost = Frontier[0]->Cost() + Frontier[0]->LastState()->Cost();
#ifdef EXPLAIN
    std::cout << Frontier[0]->LastState()->Name() << " path cost: " <<  Frontier[0]->Cost() << " transition + " << Frontier[0]->LastState()->Cost() << " estimated =  \t\t" << Frontier[0]->Cost() + Frontier[0]->LastState()->Cost() << std::endl;
#endif
    for (int i = 1; i < Frontier.size(); ++i) {
#ifdef EXPLAIN
        std::cout << ">>   " << Frontier[i]->LastState()->Name() << " path cost: " <<  Frontier[i]->Cost() << " transition + " << Frontier[i]->LastState()->Cost() << " estimated = \t\t" << Frontier[i]->Cost() + Frontier[i]->LastState()->Cost() << std::endl;
#endif
        if (Frontier[i]->Cost() + Frontier[i]->LastState()->Cost() < BestPathCost) {
            BestPath = i;
            BestPathCost = Frontier[i]->Cost() + Frontier[i]->LastState()->Cost();
        }
    }
#ifdef EXPLAIN
    std::cout << "Best path: " << Frontier[BestPath]->LastState()->Name() << ", with cost of: " << BestPathCost << std::endl;
#endif
    Frontier[BestPath]->LastState()->lookAt();
    if (Frontier[BestPath]->LastState()->IsGoal() == true) {
std::cout << std::endl << "Route: " << std::endl;
        for (int i = 0; i < Frontier[BestPath]->States.size() - 1;++i) {
            std::cout << Frontier[BestPath]->States[i]->Name() << " -> ";
#ifdef SOLVE_MAZE
            maze->setPath(Frontier[BestPath]->States[i]->X(),Frontier[BestPath]->States[i]->Y());
#endif
        }
        std::cout << Frontier[BestPath]->LastState()->Name() << std::endl;
#ifdef SOLVE_MAZE
        maze->printMaze();
#endif

        std::cout << std::endl << "************************   GOAL REACHED!   ************************************" << std::endl;
        return 1;
    }
    Path* WorkingPath;
    Path* CopyPath;
    WorkingPath = Frontier[BestPath];
    Frontier.erase(Frontier.begin()+BestPath);
    std::vector<Path'> NewPaths;
    int NoOfNewPaths = WorkingPath->LastState()->Transitions.size();
    for (int i = 0; i < NoOfNewPaths; ++i) {
        if (WorkingPath->LastState()->Transitions[i]->ToState->BeenSeen() == false) {
            CopyPath = new Path(WorkingPath);
            CopyPath->States.push_back(WorkingPath->LastState()->Transitions[i]->ToState);
            CopyPath->incCost(WorkingPath->LastState()->Transitions[i]->Cost());
            NewPaths.push_back(CopyPath);
        }
    }
    for (int i = 0; i < NewPaths.size(); ++i) {
        Frontier.push_back(NewPaths[i]);
    }
    if (Frontier.size() == 0) {
        std::cout << std::endl << "Route: " << std::endl;
        for (int i = 0; i < WorkingPath->States.size() - 1;++i) {
            std::cout << WorkingPath->States[i]->Name() << " -> ";
#ifdef SOLVE_MAZE
            maze->setPath(WorkingPath->States[i]->X(),WorkingPath->States[i]->Y());
#endif
        }
        std::cout << WorkingPath->LastState()->Name() << std::endl;
#ifdef SOLVE_MAZE
        maze->printMaze();
#endif
        std::cout << std::endl << "************************   GOAL NOT REACHABLE!   ******************************" << std::endl;

        return 2;
    }
    return 0;
}

Path

Tags

,

A path is just a bunch of Transition stored in vector. There is constructor and copy constructor, and there is a method that returns last member of vector. Each path has a cost, and since in this case paths just grow, there is a variable that holds current cost and a method to increase it by some int value.

path.h

#ifndef PATH_H
#define PATH_H

#include <vector>

class State;
class Transition;

class Path
{
private:
    int cost;  // cost of transition from start state to final state in path
public:
    std::vector<State*> States;  // list of pointers to all the states in path
    Path(State* s);  // creates path from state s
    Path(Path* p);  // creates a copy of path p
    int Cost();  // returns current cost of path
    State* LastState();  // return pointer to last state of path (accessed a lot in implementation)
    void incCost(int v);  // increases path cost by v
};

#endif // PATH_H

path.cpp

#include "path.h"

Path::Path(State* s) {  // creates path from state s
    cost = 0;
    States.push_back(s);
}

Path::Path(Path* p) {  // creates a copy of path p
    cost = p->Cost();
    for (int i = 0; i < p->States.size(); ++i) {
        States.push_back(p->States[i]);
    }
}

int Path::Cost() {  // returns current cost of path
    return cost;
}

State* Path::LastState() {  // return pointer to last state of path (accessed a lot in implementation)
    return States[States.size()-1];
}

void Path::incCost(int v) {  // increases path cost by v
    cost += v;
}

Transition

Tags

,

Transition is even simpler than state. Just some variables and a constructor. Holds the pointers to state of origin and destination, and the cost of transition.

transition.h

#ifndef TRANSITION_H
#define TRANSITION_H

class State;

class Transition
{
private:
    int cost;  // cost of transition
public:
    State* FromState;  // pointer to origin state
    State* ToState;  // pointer to destination state
    Transition(State* f, State* t, int c);  // creates transition from f to t with cost of c
    Transition(Transition* t);  // creates a copy of transition t
    int Cost();  // returns cost of this transition
};

#endif // TRANSITION_H

transition.cpp

#include "transition.h"


Transition::Transition(State* f, State* t, int c) {  // creates transition from f to t with cost of c
    FromState = f;
    ToState = t;
    cost = c;
}

Transition::Transition(Transition *t) {  // creates a copy of transition t
    FromState = t->FromState;
    ToState = t->ToState;
    cost = t->Cost();
}

int Transition::Cost() {  // returns cost of this transition
    return cost;
}

A* search and the state

Tags

,

Like a lot of people these days, i have enrolled in AI and ML online classes on Staford University.  After some talk in xkcd irc i decided to implement the A* that we learned in AI. My language of choice is C++, and i like to keep it OO. This is far from optimal, but i was more interested in general than optimal.
I won’t bother here to explain the theory behind the algorithm, just my implementation (those interested can find plenty of theory about it on internet, for instance: on wikipedia).
So let’s get started. Problem to be solved by A* can be described as set of states connected by transitions. So that’s basic structure of my code, and accordingly there are two classes, State and Transition.

State is pretty straight forward. There is a bunch of variables that are self explanatory. There is a vector of Transition, where transitions from this state are stored. There are two constructors for two specific problems (should have probably made that two different classes inherited from one, but who cares). There is also a copy constructor for the class and a bunch of methods returning values of private variables (yes i know there is better way to write those). There is one “special” method here, lookAt(), that set’s beenSeen to true and by that letting everyone know that this state has been visited before.
Nothing special, just a simple data structure.

state.h

#ifndef STATE_H
#define STATE_H

class Transition;

#include <vector>
#include <cmath>
#include <iostream>

class State
{
private:
    bool isGoal;  // is this state goal state?
    bool isObstacle;  // is this state obstacle?
    bool beenSeen;  // has this state been seen (expanded)
    int posX;  // what's the x position of this state in maze
    int posY;  // what's the y position of this state in maze
    char* name;
    int cost;
public:
    std::vector<Transition*> Transitions;  // list of teansition from this state
    State(bool g, bool o, char* n, int c);
    State(bool g, bool o, char* n, int x, int y, int c);  // creates state at position x, y which can be goal, obstacle or normal
    State(State* s);  // creates a copy of state s
    bool IsGoal();  // returns true if state is goal
    bool IsObstacle();  // returns true if state is obstacle
    bool BeenSeen();  // returns true if state has been seen
    void lookAt();  // makes state seen
    int EstimatedDistance();  // estimates distance to goal
    int X();  // returns position x of state
    int Y();  // returns position y of state
    char* Name();
    int Cost();
};

#endif // STATE_H

state.cpp

#include "state.h"

State::State(bool g, bool o, char* n, int c) {
    isGoal = g;
    isObstacle = o;
    beenSeen = false;
    name = n;
    cost = c;
}

State::State(bool g, bool o, char* n, int x, int y, int c) {  // creates state at position x, y which can be goal, obstacle or normal
    isGoal = g;
    isObstacle = o;
    beenSeen = false;
    posX = x;
    posY = y;
    Transitions.reserve(8);
    name = n;
    cost = c;
}

State::State(State *s) {  // creates a copy of state s
    isGoal = s->IsGoal();
    isObstacle = s->IsObstacle();
    beenSeen = s->BeenSeen();
    posX = s->X();
    posY = s->Y();
    Transitions.reserve(8);
    for (int i = 0; i < s->Transitions.size(); ++i) {
        Transitions.push_back(s->Transitions[i]);
    }
    name = s->Name();
    cost = s->Cost();
}

bool State::IsGoal() {  // returns true if state is goal
    return isGoal;
}

bool State::IsObstacle() {  // returns true if state is obstacle
    return isObstacle;
}

bool State::BeenSeen() {  // returns true if state has been seen
    return beenSeen;
}

int State::X() {  // returns position x of state
    return posX;
}

int State::Y() {  // returns position y of state
    return posY;
}

void State::lookAt() {  // makes state seen
    beenSeen = true;
}

char* State::Name() {  // returns name of state
    return name;
}

int State::Cost() {
    return cost;
}

Follow

Get every new post delivered to your Inbox.