impossible terrain - path finding crash

[tabanli]

During this tourney, I always misclick with my Flyer-Snake-Hero stacks and wait for the path finding algorithm to find a suggestion which usually takes very long time and crashes once in a while. The algorithm still makes suggestion by using X X X for the impossible terrain. Wouldn't it be easier to have an immediate pop-up if the terrain is impossible.

[SnotlinG]

There is some logic for this, but obviously it isnt working so well
Ill investigate

[SnotlinG]

I just did some testing (and checking my code ).
The problem here is that if you click on a tile that has impossible terrain, you will immediately get a popup informing you of this (easy to test). But if you click for example on a city, then this is valid terrain for all units in your stack (SeaCreature / Flyer / Hero), so the pathfinding algorithm is trying to find a path there. So if the city is located on an island with no sea/swamp connection the pathfinding will not find any better path than moving through the impossible terrain (for the seacreature) to move to the city.

Im actually not sure how to solve this better. It would be possible to check all adjacent tiles around the city first before kicking of the pathfinding algorithm, but that would not guarantee we get rid of this issue (city with some few swamp tiles adjacent would still fool it), as well be an extra check needed to run everytime you click a path to a city.

[tabanli]

Very interesting situation. I don't see an easy solution either. But usually these are misclicks where we forgot to deselect the snake.

[Chazar]

An Abort-Pathfinding-Button would be neat, but not sure you can realise it in a browser.

Actually, instead of a new abort button, it would be even better if another click elsewhere restarts pathfinding on that new location (ie restart rather than abort).

[Chazar]

Otherwise, forgetting to deselect the serpent did really happen often to me in the tournament games, and it is pretty annoying.

So would it be feasible to spent one more integer field per map tile, or is 2k additional memory per map a problem already (less for smaller maps)?

During map creation, one simply enumerates all water areas and saves the area number with each tile (lava areas could be enumerated here as well). Pathfinding then starts checking whether the starting and target tile carry the same area number, if a water-only creature is in the stack, and aborts right away if the numbers are different. That checks requires constant time, ie is practically free. Computing the areas is at most quadratic, but is only done once when the map is created. So the only real cost is one more integer field per tile when transmitting the map from server to client.

[tabanli]

I think the city terrain is the real problem. Think about a map divided by two rivers going north to south which divide the land into three parts, west, center and east. It is possible for a snake at a river neighbored city at west to have access to a river neighbored city on east but it is entirely possible that it is has no access whatsoever. It is easy for human to see but think very hard for computer, think about all the useless permutations computer is checking to arrive to the result.

[Chazar]

No, city or swamp terrain does not affect my proposed solution of enumerating all water areas internally upon map creation. I can provide more details, if this solution seems sensible.

[SnotlinG]

Chazar, the solution seems interesting, and is probably the best approach so far. But I see some possible issues:

If you have 2 fields of water, and they are connected either by swamp or cities, should they then be counted as the same field of water or not? This as seacreatures can move between them, but ships cannot.

The risk is that we make a solution that only works for some special cases. Lets say as a hero-stack you have seacreature/ship/hero, then clicking on sea1 when you stand on sea2 it is impossible to find a path if the seas are connected only with swamps, but if you didnt have the ship in your group a path would be possible.
Or if the where connected via Swamp only but with 2 Ports at the proper places(next to the swamp) a path would be possible.

Any feedback/ideas/etc? Bring it on

[Chazar]

That is not a problem.

However, let us first be clear on the goal here: I suggested to add a fast (=constant-time) check to determine whether the existing pathfinding algorithm can find a solution at all. I did not suggest any improvement to the actual pathfinding algorithm, only a shortcut if there is no path at all, which is expensive to determine through the actual pathfinding algorithm itself.
Result: If there is a path, then the overall computation will be a tiny fraction of a second slower, if there is no path, then it will be a lot faster.

The general solution for the Swamp/Water problem that you mentioned would be to enumerate each kind of movement area separately: So each map tile would then be associated with one number per movement area kind, e.g. one number for boats, one number for aquatics, one for ashwalkers, one for landlubbers, etc.
The proper pathfinding algorithm is only started, if the area codes of the starting and target tile are identical for each movement area kind that the stack contains (i.e. 2 integer comparisons, if the stack contains both boats and aquatics).

This general solution should cover all problems of that kind. The check whether or not to start pathfinding is still fast (constant time), but it requires you to associate each map tile with a vector of numbers, the vector having a size equal to the number of different movement kinds available in the game.

However, if memory is a concern, you can do better here:

First of all, boat movement areas are always a subdivision (partition) of aquatic movement areas: an aquatic creature can always go where a boat can go. Whether two boat areas are within the same aquatic area is thus an equivalence relation. Therefore, you only need to store the representatives for each boat area code.
Put simply: you only need to enumerate the boat movement areas, and all contiguous aquatic areas that cannot be used by boats. Then, you create a finite mapping from boat area codes to aquatic area codes (i.e. in Javascript probably just an int-array, having the size equal to the number of different boat area codes).

If the stack contains a boat and aquatic unit, then you just compare the boat area code and abort if they are different. Otherwise, if the stack contains just an aquatic creature, then you map the boat area codes to aquatic area codes and compare them, again aborting if they are different.

Example: Say we have an ocean, next to a swamp, next to a city, next to a swamp, next to an ocean; a separate ocean; and a separate swamp. The first ocean gets its own number, say 0; both swamps and the city are connected to each other, so they all get area code 1, the second ocean receives number 2, the third ocean number 3 and the final swamp number 4. There are 5 boat areas, so our array has 5 entries. Since the first three are connected to each other, we also compute the array [1,1,1,3,4] (instead of 1, we could have picked 0 or 2, yielding [0,0,0,3,4] pr [2,2,2,3,4]).
Now if we have a stack consisting of both boats and aquatics in the first ocean, targeting the second ocean, we simply compare the numbers: 0 is different from 2, so no path possible, abort.
If the stack only contains aquatics, we look up the numbers in the array: 1 is equal to 1, so we know that a path is possible.

The same mechanism can also be used for land based movement, in case of land masses that are entirely separated by lava/mountains or absence of ports on islands. Like water/aquatic, one enumerates all contiguous land areas, and computes an array of representatives, mapping land area codes to a common representative area code if they are connected through ports. This may be then used for stacks that contain just boats, but no aquatics.

However, I don't think this is a must have: since the original pathfinding remains unchanged, each movement area kind is a nice-to-have, but not a must-have: if it is there, it might shortcut impossible path finding; if it is not there, then one needs to wait a little longer in that special situation that is not cover, but there is no error!
For example, one could have area codes for flyers, but I don't think this pays off, since maps rarely have an airspace divided by lava, that players would actually want to move into.


Second, mutual exclusive movement types might use the same vector index, e.g. lava and water areas are mutually exclusive, so their codes could use the same index in the area code vector per tile. However, such special cases always bring the danger of errors with them, and I don't think that is worth it, just to reduce the vector size by one - it's not that much memory. (Maybe land and water could use the same area index, with just two different arrays for the representative arrays for aquatic and land/boat areas, but cities might take some extra thinking...not worth the trouble unless you are really worried by memory usage for maps.)

Possible Problems remaining:

• One-way movement:
  The above method cannot deal with one-way movement. So you have a problem if you want to allow aquatic creatures to move across waterfalls only downriver, but not up. From what I read thus far, it seems very unlikely that Warbarons will offer such one-way movement in the future.
• Stranded Heroes: Consider a water-walking hero, which was dropped off by a magic dragon in some mountains by the sea. Treating him like an aquatic creature only would wrongly abort pathfinding, since the mountain and the sea will always have different area codes. So lone water-walking heroes should always use proper pathfinding, without shortcuts by comparing area codes.
  I hate these special cases, but it seems the easiest fix if you also intend to use area codes for land-based movement. There are other fixes for this situation, since the hero can move at most one square before the usual situation is reestablished, but they are probably not worth considering.

Disclaimer: These are just my naive ramblings on the topic, and I welcome any further insights and discussion. I am not at all an expert on pathfinding algorithms!