nathansttt / hog2

Pathfinding and search testbed/visualization suite. Current code is in PDB-refactor branch.

HOG2

About the Project

HOG2 (Hierarchical Open Graph 2) is a collection of classes and a tile-based simulator which are designed as a simple model of RTS and other clocked simulation environments.

Documentation (much of it older, but starting to be updated) is available here.

Getting Started

To get started with the HOG2 applications run the following commands. Note that SFML and OpenGL are not required for the headless version of HOG2 (see build instructions below.)

Prerequisites

Linux

On Ubuntu run the following command:

# apt install build-essential libglu1-mesa-dev freeglut3-dev libsfml-dev

On Debian run:

# apt install git libglu1-mesa-dev freeglut3-dev libsfml-dev

On Arch run:

# pacman -S git base-devel mesa glu freeglut libsfml-dev

On CentOs and Fedora run:

# yum install git make gcc-c++ mesa-libGL-devel mesa-libGLU-devel freeglut-devel libsfml-dev

MacOS

Download and install XCode from the App store.

Windows 10

TODO

Building

To build the project on the command-line, you must first download the source code:

git clone https://github.com/nathansttt/hog2.git`

Then traverse to the build directory with:

cd hog2/build/SFML # cd hog2/build/web for the web version

Finally, build the project with make:

make

Alternately, you can build a headless version of HOG2 (which does not require SFML or OpenGL) using:

make OPENGL=STUB

Note that when switching between the headless and GUI versions of HOG2 you must do a clean rebuild.

After this completes the binaries can be found under ../../bin/release/.

To build using XCode you can open one of the projects in build/XCode. HOG2 ObjC contains a full sample application; many demos are available inside the hog2 mac native demos project.

Installation

Typical research usage of HOG2 would not involve installing applications from HOG2.

To fully install the programs to /usr/local/bin, run sudo make install under the hog2/build/gmake/ directory; to uninstall run sudo make uninstall in the same directory. The installation location can be changed with make install prefix=</path/to/dir>.

Licence

HOG2 is open source software licensed under the MIT license

hog2's Issues

Is pdb-refactor good to use?

I notice that the pdb-refactor branch is a few hundreds of commits ahead of master. Is it appropriate to use it or better to use master?

ParallelIDAStar does not mimic IDA* expanded and generated nodes at the last layer

The current version of ParallelIDAStar attempts to mimic the work done by IDA* but get the speedup of parallelization. That is evident in the termination condition which was explored a bit in PR #73.
For all layers except the last, the generated and expanded will be the same as both algorithms expand all of the nodes. But, in the last layer, they will probably expand less than all of them as a solution is found.
When looking at the way that the number of nodes expanded/generated (link), all the nodes that were expanded in the last layer are added, even those that were done by threads which are expanding nodes that would have not been reached by IDA*.
Now, these are indeed generated and expanded nodes that should be accounted for, but it might create a difference in results when trying to only get a speedup and not change the behavior of IDA*.

Invalid Characters in file names in build/XCode for Windows

Greetings,
Some of the file names in buid/XCode contain asterisks in their names, making them invalid paths in Windows and create problems when cloning and working with the repo.
An example for such file is: https://github.com/nathansttt/hog2/blob/PDB-refactor/build/XCode/hog2%20iPad/IDA*%20-%20IBEX%20copy-Info.plist
I am not sure how to address this and thus opened an issue instead of a pull request containing an appropriate fix.
Kind regards,
Lior.

Incorrect ParallelIDAstar Result When C*<workDepth

The following program shows a case where C*=2, but PIDA* returns 12.

#include <cinttypes>
#include <iostream>
#include "MNPuzzle.h"
#include "ParallelIDAStar.h"

int main(int argc, char *argv[]) {
    MNPuzzle<4, 4> env;
    MNPuzzleState<4, 4> start;
    MNPuzzleState<4, 4> goal;
    env.ApplyAction(start, kRight);
    env.ApplyAction(start, kRight);
    std::cout << "Start:" << start << std::endl;
    std::cout << "Goal: " << goal << std::endl;
    ParallelIDAStar<MNPuzzle<4,4>, MNPuzzleState<4,4>, slideDir> ida;
    std::vector<slideDir> solution;
    ida.GetPath(&env, start, goal, solution);
    std::cout << "Optimal cost: " << env.GetPathLength(start, solution) << std::endl;
}

Gives the following output:

Op order: Right Left Down Up                     
Start:(4x4)1 2 0 3 4 5 6 7 8 9 10 11 12 13 14 15 
Goal: (4x4)0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
66 pieces of work generated
Starting iteration with bound 2.000000; 56 expanded, 176 generated
Starting iteration with bound 4.000000; 56 expanded, 176 generated
Starting iteration with bound 6.000000; 56 expanded, 176 generated
Starting iteration with bound 8.000000; 56 expanded, 176 generated
Starting iteration with bound 10.000000; 61 expanded, 193 generated
Starting iteration with bound 12.000000; 101 expanded, 313 generated
Optimal cost: 12

This is likely because there is no goal check in GenerateWork() (or later in StartThreadedIteration()).

Missing <cinttypes> in ParallelIDAstar

When creating the example for Issue #70 I failed to compiled the file.
The cause is PRId64 in a few printf in the file as this requires to include but it is not included in ParallelIDAstar.
The issue was probably not found before because often when importing ParallelIDAstar, PDBHeuristic is also imported, which does contain .

What is the function of "bucket" in the scenario?

As introduced in https://movingai.com/benchmarks/formats.html, the first column of .scen file means "bucket". But there is no explanation about "bucket".
"bucket" is used in ScenarioLoader.cpp and ScenarioLoader.h but I still have no idea how to use "bucket".
https://github.com/nathansttt/hog2/blob/PDB-refactor/apps/canonicalGrids/Sample.cpp will do something if bucket > 0 but the value of bucket is not used.

I notice that, in general, the greater bucket is, the greater optimal path length will be but this is not always true in the scenario file.

Thanks in advance.

MNPuzzle Create_Random_MN_Puzzles uses non-existent constructor

Link to the problematic line.
It seems that there is no constructor that accepts (int.int).

Missing <stdio.h> for printf in FixedSizeSet.h

FixedSizeSet.h uses printf but does not import stdio.
I had a problem compiling when stdio was not included in the cpp file which used FixedSizeSet.

Hashing in LexPermutationPDB for Large States is Faulty

The following code demonstrates that for large enough state spaces, the hash is no longer unique and when hashing a state and then trying to get it back from the PDB results in faulty states.

#include "PancakePuzzle.h"
#include "LexPermutationPDB.h"
#include <iostream>

int main(int argc, char *argv[]) {
    const int numPancakes = 30;
    PancakePuzzleState<numPancakes> state;
    PancakePuzzle<numPancakes> env;
    std::vector<int> bucketPattern;
    std::vector<int> dataPattern;
    for (int i = 0; i < numPancakes; i++) {
        if (i % 2 != 0) {
            dataPattern.push_back(i);
        } else {
            bucketPattern.push_back(i);
        }
    }

    srandom(0);
    for (int x = 0; x < numPancakes; x++) {
        std::swap(state.puzzle[x], state.puzzle[x + random() % (numPancakes - x)]);
    }

    LexPermutationPDB<PancakePuzzleState<numPancakes>, PancakePuzzleAction, PancakePuzzle<numPancakes>> bucketPdb(&env,  state, bucketPattern);
    LexPermutationPDB<PancakePuzzleState<numPancakes>, PancakePuzzleAction, PancakePuzzle<numPancakes>> dataPdb(&env, state, dataPattern);

    uint64_t bucketHash = bucketPdb.GetPDBHash(state);
    uint64_t dataHash = bucketPdb.GetPDBHash(state);

    PancakePuzzleState<numPancakes> dataState;
    PancakePuzzleState<numPancakes> bucketstate;
    bucketPdb.GetStateFromPDBHash(bucketHash, bucketstate);
    dataPdb.GetStateFromPDBHash(dataHash, dataState);
    std::cout << "State: " << state << std::endl;
    std::cout << "Bucket State: " << bucketstate << std::endl;
    std::cout << "Data State: " << dataState << std::endl;
}

Which gives the following output:

State: 13 10 11 28 5 15 16 8 2 19 12 20 26 4 17 6 1 27 22 9 21 29 7 25 0 23 3 24 18 14 
Bucket State: -1 8 0 -1 12 28 16 -1 -1 -1 -1 -1 -1 -1 2 4 -1 -1 -1 -1 18 22 14 26 10 24 20 -1 6 -1
Data State: -1 9 1 -1 13 29 17 -1 -1 -1 -1 -1 -1 -1 3 5 -1 -1 -1 -1 19 23 15 27 11 25 21 -1 7 -1

Highway dimension

Is it possible to use this to measure the highway dimension of an arbitrary graph as described, say, by an edge list?

Bug When Accessing a PDB from a Heuristic Pointer in Parallel

This error was observed for LexPermutationPDB, but assumed to be applicable to MR1PermutationPDB due to similar structure.
The error will therefore also be explained using LexPermutationPDB.

1. When calling LexPermutationPDB through a Heuristic pointer, we call HCost(). This calls HCost() from PDBHeuristic (link).
2. This in turn calls GetAbstractHash() which is implemented in LexPermutationPDB (link) which then calls GetPDBHash().
3. In GetPDBHash() (link) uses locsCache and dualCache in index threadID. Note that by calling it through HCost(), we are unable to specify the threadID, which means it defaults to 0 as per its decelration (link).

This means that calling the PDB from a Heuristic pointer always inputs threadID=0, which causes problem when multiple threads are using the PDB, as they all change the same vector at the same time instead of changing their individual vectors.

Windows Invalid Characters Left in Some Paths in Filenames

This is a followup to issue #57 and commit fc8635f which addressed most of them, but not all.

Some files are left with a '*' in there name which are as follows:

• build/XCode/hog2 iPad/hog2 iPad.xcodeproj/xcshareddata/xcschemes/IDA* - IBEX.xcscheme
• build/XCode/hog2 mac native demos/hog2 mac native demos.xcodeproj/xcuserdata/nathanst.xcuserdatad/xcschemes/A* (Graph).xcscheme
• build/XCode/hog2 mac native demos/hog2 mac native demos.xcodeproj/xcuserdata/nathanst.xcuserdatad/xcschemes/A* (Map).xcscheme
• build/XCode/hog2 mac native demos/hog2 mac native demos.xcodeproj/xcuserdata/nathanst.xcuserdatad/xcschemes/IDA*.xcscheme

FFBDS.h uses env instead of h to determine the HCost of a pair

Greetings,
FFBDS is provided with both an environment and a heuristic. It is supposed to choose its next pair based on the heuristic it got, but instead uses the heuristic on the environment it got. It works if the same environment is provided both as the environment itself and the heuristic, but will fail given a different heuristic.
The problematic line is FFBDS.h:316.
Kind regards,
Lior.