ok lets get technical, to be honest i am not sure if i really understood the concepts you are talking about completely, but i will try to show how the current algorithm works:
(Always keep in mind, i am more artist than coder, and my math class is several years ago =P)
The base is the point/triangle-collision detection. I choosed this over rectangles (which are defintly easier to compute, cause it enables me to layout a better fitting mask. Also i didnt used circles (which would be really easy to setup a algorithm cause i could use the already existing code for checking the distance to a party) cause they either would overlap or have spaces between them and as far as i know extracting a root is really expensive in terms of computation.
Instead i used the following grid setup:
You see i covered the whole map with 22 triangles.
The algorithm to check for the collision can be found here:http://prophesyofpendor.forumotion.net/t870-triangle-point-collision-detection-algorithm
To check for regions i did the following algorithm:
if test fails
So basicly i drop out of the test as soon as i find the matching triangle (best case 1 check, worst case 22 checks)
based on this test i know now which region i have and can pass this as variable
now the speed_multiplier script works the following way:
- it will get called automatically everytime the games needs to check the skill modifier (this is a hardcoded behaviour)
- currently i check for the type of party and if its not a kingdom_hero_party i drop out (to save computation time)
- now i gather information : i run once the above region algorithm for that party
- based on that i change the modifier
thats it basicly
The main problem is that the game calls this speed_multiplier script several times per second for each party on the map that needs the skill modifier (its not documented if only walkable partys call this or also stationary ones, could be tested tough)
This means that in the worst case scenario every party checks 22times the collision with the triangles (assuming all partys gather in the last triangle) per second.
Now i wanted to avoid to get this too complicated, and i am really not sure about adding another grid above this - but i am of course open to ideas.
As far as i see it: the region test is the real bottleneck (with 22 checks in the worst case).
And this grid you mentionend could of course help to minimize this. But to be honest, i have no clue how to set it up and if its really needed.
I think its pretty optimized for now (its just way too many calls when i use it for every party)
The thing is: as soon as i use this filter (only allowing kingdom_hero_partys for example) this runs very smooth.
And for the main stuff thats all we need.
Now i was thinking more about the grid, its actually a neat idea... a very simple aproach would be to just use a 2x2 grid
(no extra data needed, i can hardcode this into the scripts) which would turn down the number of calls for the collision detection from 22 to 10 in the worst case. Not bad, guess i will try this.