Hilarious trouble

A I predicted in the previous post. Precalculation algorithm gone wild.

Theoretically, if the map is completely free, game should make about 40 millions of pathfinding calculations per Z level(!).

Of course, it is impossible to have such map, but frankly, even halve of this quantity is enough to dream about painful execution for the author of the game.

How do I plan to fix that?

First of all, we don’t have to do all calculations every sing time.

For example we have this tiles:

1 2 3

4 5 6

7 8 9

We have done calculations for clusters 1-4 and now, we start cluster 5. We don’t need to recalculate its connections with clusters 1-4. Because, if the check said, you can’t reach cluster 5 from cluster 1, it works vice versa, doesn’t it?

Good, we cut good the load of calculations!

Next step Is multithreading, I mentioned before. I tried It already for couple of times and was really amused.

Yes, I knew that multithreading ≠ multiprocessing, but on the application level it is nearly the same.

 Modern multicores CPU are great doing tons of routine calculations simultaneously. You just have to help it a bit and designate them for this. My plan is to cut map into smaller units. For example 10 blocks and start every single block as thread.

It would make CPU to work hard on it. We have main thread free and would entertain player writing about game lore and world, that has been generated.

As for me, I can wait even a dozen of minutes or more, if the game tells me what is going on, what cool stuff it generates and doesn’t just look dead.

I really want to finish it ASAP and start drug&drop.

Traveling is nearly to be done

Predictable. This is the word for all this 'pathfinding' routines.
Surprisingly predictable. Everything gone just the way I described in previous posts.

Inhabitants of Cold Halvic (about 40 NPC) gathered together and started their long-long trip to another settlement.
They successfully arrived to their destination. Of course, there were few glitches as I predicted, but predicted glitch isn't a problem a all.

So, I have to create 'ban direction precalculation' and 'add NPC to active zone' (because now, Player can see NPC appear and disappear from/to nowhere. That is fun to see during test, but not during the actual play).
Also, we get the nice bonus from this road map routines. You are to be able to click on the mini map or the global map and expect your character to go there on his own. Saving this destination and having 'beacons', just like in Dungeon Craw SS would be great! This automove and autoexplore features are my favourite in DCSS. Removes tons of micromanagement.

Yeah. I think, I can finish it today and move forward to finalizing the ranged weapons.
After this, I have to start, long awaited 'drag&drop' routines. They wouldn't do themselves!

PS
Also. I have to share another good news. Jesus05 the fellow and devoted roguelike developer joined our team.
It would be great to have him on board, because he is the guy I used to ask for advise for many times. 
He is a programmist. So, we set up a version control system and try to work together.
Of course, it would take a time to set it all up and he should read my supermegacode first, but, I think it would enhance the development.

Second test

Second part of the tests.
Game gave order to the group of the settlement's inhabitants to move to another randomly selected settlement.
The random settlement can be anywhere on the map.
I followed them, of course.
They gathered at the some random point inside of their settlement, it could be even the far corner ^_^.
Then, game was changing next 'beacon point' every 6000 turns.
Of course, we were losing NPC during this exodus - stragglers, guys who wanted to step on the each other position and so on.
It looked less like army unit on the move and more like carnival. Because NPC were selecting different positions inside the beacon, every single move.
Also, this 'trip' showed flaw in pathfinding algoritm. It worked well in a short distance, but when we have huge catacombs, it can go looking for path to some sideways alley and clutter itself. 
Another variant, algorithm can find the right way, but it would be rather long one. 
For example 3000 tiles.
Sounds Okay? Then repeat it for all creatures of the group every turn.
I am not saving the whole path for then creatures, because don't find it reasonable.

I had other idea.  Thanks to road map we have now.
This algorithm:

1. Every time, when creature has to find its path from A to B game will make raw calculation, how far this coordinates  from each other. 
if  (abs(x1-x2) + abs(y1-y2) ) > N goto (RoadMap search)

okay, B stays in a reasonable range from A, Lets try standard  pathfinding.
This pathfinding has interation limit set to X.
If it founds the path -- hurray! Let move the creature (END)
If it couldn't find path soon enough, we don't want to bother any longer and go to (RoadMap search)

(RoadMap search)
We will make a pathfinding search on a road map.
First of all, we check the creature. Are you at road map? If no, it means that poor fellow was bugged and dug into the wall. It occurs from time to time. I am embarrassed. 
If Not at road map, then start some debug routines and END the pathfinding. There is no catch for this creature.

If it is okay, we will found nearest coordinates, that would eventually bring our creature to its destination.
Of course, they aren't 100% precise, but we don't want them to be so precise, we want creature to move in to thee direction of its goal as soon as possible.
If it wouldn't 100% precise, it would be even nicer, because creature would be more lively, that straightforward AI ruled android.
And then, we will start our short-ranged pathfinding again.It would work well, this time.

PS. Theoretically. Road map can fail, if two clusters would be considered linked , when they are not. For example, they would have long 1 tile wall between then or at one of them. I'll think about this potential issue later. 

EDIT: I found the solution. We would make precalculations. Find short path from every empty tile of one road map unit to another. If at least one misses to onother - ban this direction for global pathfindig.
EDIT2: Also, it would be great idea to move pathfinding calculations for 'out of screen' NPC to another thread and implement them in bulk, when they are done.Theoretically, few creatures may decide to move to one tile. But it wouldn't happen on the screen! Other creature got your cookie? Better luck next time.
The same thing is for groups of creatures. I think I'll do this now, because groups doesn't have any visible representation on the game map and store all data inside their own classes. They just prepare calculations, that would be used for creatures in future. No possible conflicts at all!

Test of the road map

At the end of all, I managed to do some tests. Definitely, my new job is rather cool, but when I come home I don’t have spare brain power for my own projects.  

Good news, today I managed to test first part of the Road Map algorithms.

Test routines gave inhabitants of the first settlement on the map (it is starting location of the player) order to move to one random location, adjustment to their settlement and was changing this goal location once per 6000 turns.

Frankly speaking, it was the location at the settlement borders.

All townspersons act well, they moved from one point to another like one unit and were fighting upcoming necromutants.

It means that road map routines work well for the creatures within the activity range of the player.

Next step – I have to work with situations, when creatures would enter the current activity zone from ‘offline’ area.

Road map

Fallen has huge world. That's it.

When I was choosing the platform, I have mobile and PC on my table.

Mobile is cool! It is potentially the strongest 'marketing' decision, but it has it's own limitations.
Big computer, from other hand, has 'gift of power'. The simplest notebook has overwhelming resources for the roguelike game.
Last year I weight all pro and contra and take the side of big computers.

From this point, I found that it is rather silly to use PC as platform and fight for every kilobyte, because it is 'great tradition of roguelike development'.

Yeah, yeah. One of that, I hate so ugly.

Of course, we can battle the level design and make game, that wouldn't take more that couple of megabytes of the memory and be so proud of it.

Who cares, lol.

Players want to play game. Run it on their computer and have fun. Nobody cares, how many gigabytes of operative memory would stay empty and hollowed, while he or she plays the game.
That's why I decided to use PC and utilize it's vast resources. Game eats up about one gigabyte of the operative memory. It simply keeps everything in memory an has huge maps. All world are in play, every second.
It gives great possibilities, I'll wrote about them, but has its drawbacks.

One of them – pathfinding.

If one creature tries to find path from point a to point b, when the range between them is about 200 tiles, it is no problem.
It would be done on fly.
But, if the group of 100 creatures wants to take a million tiles long stroll?
Heh. Easy. I shouldn't reinvent the bicycle. It has been done thousands of times before Fallen.
First of all.
They move as unit. It means that unit does all long-distance checks, when single creature looks for the path to units position or its position in formation.
Part two, until player stays close, they don't literally move using standard algorithm.
Unit just pull out all its creatures like carrot and replant somewhere else in a bulk.

And the last, but not the least – the road map.

When map has been generated, the game creates the road map – highly abstract copy of actual map at 20x1 or 30x1 scale. Tiles of this map aren't complicate. They are just true or false, can go or not.
Unit looks for its goal on this map and select closest tiles block, where it would tell it's creatures to go. It isn't a strict order. Creatures is going to follow it, if they don't have anything important at their hands, like fighting. It means, that guards patrol will help you to fight this monsters, but wouldn't stay there forever and will go away. You can follow them for your safety, but it is your choice.

Heh. That's the story. This routines are useless and burdening if you have small maps, of course.

Road map in Fallen, you ask?
Finished and correct.
Now I have to test pathfinding and let creatures' groups to move all over the world of Fallen!

Pathfinding

While working on inventory patch, checked another "bottle neck" of the game - the Pathfinding.
It is really nasty algorithm, you know. It has dozen of repeating iterations, and this algorithm should be run for every active creature (of course, it can be simplified, if monsters can be grouped into units and they would use short ranged pathfinding up to group center, but we have roguelike nor strategy game. -_-).
So, pathfinding is real bottle neck of every roguelike project.
I check mine and started refactoring.
Refactoring isn't finished yet, but algorithm works at least 5 times faster then before!
It means that Inventory patch would also be performance patch, nice ^_^!