Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[jaked122]

Spoiler: distance stuff (click to show/hide)

Hey guys, look at the heatmap that it generated. These two levels are parts of the same blueprint. Isn't it great?

[porque]

Damned Floyd-Warshall algorithm. Only if I stored the nodes in a vector instead of an associative array.

Why are you using Floyd-Warshall? Using Dijkstra's algorithm (n times) is faster for sparse graphs.

[jaked122]

Dijkstra's isn't really necessary as it is an unweighted graph, Floyd-Warshall's is just easier to implement, and I wanted to see if it would reflect the situation in the game(it does, sort of).

Anyway, I've made it a good bit faster(and now it can be stopped). In any case, I should be using Johnson's Algorithm, which runs in O(|V|²) versus O(|V|³).

In any case, I should use BFS in this instead of Bellman Ford or Dijkstra's in Johnson's algorithm because it's an unweighted graph, so it doesn't really need any of that fancy stuff, so I suspect that it will go even faster... No, linear time over each node for every node is still O(|V|²).

[Symmetry]

but the description of johnson's with no negative weights is just djikstras?

If you want it to be faster I would use something like jump points pathfinding to handle the large open spaces.

[jaked122]

I'm currently using BFS instead of Djikstras because it is an unweighted graph. It certainly looks like Jump Point Pathfinding would improve the performance further, but for now it can handle up to 8000 points without too much time spent(though it does use a lot of memory atm), and that's using a plainly stupid method of finding adjacent spaces, just looking through all the offsets that a given designation type could produce(minus ramp, that will take some additional work).

Heuristics complicate things more than I'd like until development is further along, it also results in the sort of issues that DF has problems with given that adjacent squares between z-levels are preferred when closer items are available on the same level.

In any case, right now it looks at the average of the distances between points, but if we're optimizing a fortress so that the longest paths(worst case),  it might be better to output the maximum distance instead.

What do you think?

[jaked122]

You seem to support X and Y mirror symmetry. Might I request a 90 degree rotational symmetry option?

I realized that it would be very easy to add 90 degree rotation to the program, contrary to my belief earlier.

As it turns out, rotating this way iteratively is as easy as setting the x to -y and y to x.

In other news, building it on Travis-ci is remarkably difficult, as it turns out, Travis-Ci doesn't support any of the libraries it requires.

I don't feel like dealing with any of that for now, so have another Linux x64 release.

Some day I'll get around to making some decent documentation, but that's in the future.

[Arlax]

Awesome! This is so helpful. I've been using dwarf mockup for some time, but the lack of a symmetry tool bothered me. Thank you.

[khearn]

This sounds like the Princess bride swordfight at the top of the Cliffs of Insanity.

You are using Floyd-Warshall's algorithm, eh?
I thought it fitting, considering the associative array.
Naturally, you must expect me to use Djikstras.
I find that Johnson's cancels out Djikstras, and runs in O(|V|2) versus O(|V|3).
Unless, the programmer has studied his Bellman Ford, which I have!

[expwnent]

Posting to watch.

[se5a]

This sounds like the Princess bride swordfight at the top of the Cliffs of Insanity.

You are using Floyd-Warshall's algorithm, eh?
I thought it fitting, considering the associative array.
Naturally, you must expect me to use Djikstras.
I find that Johnson's cancels out Djikstras, and runs in O(|V|2) versus O(|V|3).
Unless, the programmer has studied his Bellman Ford, which I have!

+1

[Boozeanator]

Thank you; looks like a cool program. I have tried only the most basic example because I don't have time to play right now, but it does work .

Install on Linux Mint 17.1 (a Ubuntu derivative).

Quick notes:

1.
I installed SFML with
sudo apt-get install libsfml-dev

2.
The cmake in the Ubuntu repos isn't recent enough. I downloaded and compiled it myself (the address is in install_dep.sh, a shell script which probably could have done the job for me, but whatever). I gave the --prefix=path argument to ./configure to get the more recent version of cmake to install inside Symmetricality's folder so it didn't pollute my system.

(I also added the files I downloaded to .gitignore, although this is optional.)

wget https://cmake.org/files/v3.4/cmake-3.4.1.tar.gz&&tar xf cmake-3.4.1.tar.gz

cd cmake-3.4.1/

./configure --prefix=whatever

make -j2

make install

cd back_to_symmetricality

export PATH=path/to/new/cmake/bin:$PATH

which cmake => new one

cmake --version => new one

cmake .

(Want to do make next; but one more thing first ...)

3.
I got a compilation error:

Scanning dependencies of target Symmetricality
[  9%] Building CXX object CMakeFiles/Symmetricality.dir/PlanRenderer.cpp.o
/home/NAME/OpenSourceProjects/Symmetricality/PlanRenderer.cpp: In member function ‘void PlanRenderer::loadDesignationConfiguration(Json::Value&)’:
/home/NAME/OpenSourceProjects/Symmetricality/PlanRenderer.cpp:474:42: error: ‘const class sf::Color’ has no member named ‘toInteger’
                     if (sf::Color::White.toInteger() == pp.toInteger()) {
                                          ^
/home/NAME/OpenSourceProjects/Symmetricality/PlanRenderer.cpp:474:60: error: ‘class sf::Color’ has no member named ‘toInteger’
                     if (sf::Color::White.toInteger() == pp.toInteger()) {
                                                            ^
make[2]: *** [CMakeFiles/Symmetricality.dir/PlanRenderer.cpp.o] Error 1
make[1]: *** [CMakeFiles/Symmetricality.dir/all] Error 2
make: *** [all] Error 2

Fixed by changing line 474:
-                    if (sf::Color::White.toInteger() == pp.toInteger()) {
+                    if (sf::Color::White == pp) {

Now we can make to build Symmetricality, and it runs and works.

Probably an API change in SFML?

Thank you again XD.

[crazyabe]

PTW

[jaked122]

Guys, I made a different thing


It was in development, but then I realized I had no desire to implement the path generation stuff in it. It is... more symmetry focused, with lots of other useful features, like building designation inline with designation designation.


You should try that instead.