Will we be able to create own mods for the flowfield?

Mine gets the right answer, up until the goal's cost is sqrt(2) higher than any of its neighbours.

Wait. Crap. Cells further away that have even lower costs are getting preferential treatment.

I don't think distance from goal works very well. Distance-squared gives nicer results, at least in Excel.

Been there, done that, got the grade. ;P Going to the side of a hill is going to be weird because your expected minimum from the distance field is now no longer quite the minimum because of the hill. It's one of those 'build the field carefully' moments. Also, the diagonal being 1 cost is going to mainly super encourage diagonal movement. So diagonals across hills are slightly better looking.

are the flat tops of your hill inheriting the cost of the steep sides?

So I now see that it's nearest-lowest cost, and I understand the tradeoff is that it's not always globally the lowest, but surely that doesn't always result in correct pathing? I think we saw an example of that in the live stream where the unit got trapped in a crescent, because getting out of the crescent would cost more.

Exactly why it is a debug simulation, there for him to figure out how to tweak these little variables on the Flow Field calculation and generation until units naturally avoid systems like that. And in the final implementation they may attempt to make the unit ignore the distance cost of it's next step until the variables change in the right way that they can say it would be able to start following the Flow Field again.

Sorta, "if you are stuck here, ignore your goal until you find a lower cost area"... Though that seems dumbly inefficient, so alternatively they may have emergency traditional pathfinders for the rare cases where this happens.

it probably changes the algorithm that creates the flow field so that gaps like that are derived from the closes point out instead of the nearest point to the goal.

Ahhh, yeah, that's basically how you'd do it, the problem is finding the closest point out. in some instances it'd be easy, with a little crescent moon you'd just have to check a radius of dots around the unit then set an artificial waypoint to get that point, before it continued on it's initial journey.

But if instead, you have a... why is the only word coming to mind "phallus"... shaped plane area, bordered by mountains, and eight or so units get caught in there, with their goal on the other side of the mountains, then "Out" of their predicament is a long way away. And finding that "nearest point outside of it" is pretty much required to be traditional pathfinding, as far as I can tell.

However... That's a clever thought, and since I'm assuming the guy who wrote the article that was the centerpiece of the book is a better programmer than me, by far, if it's possible, he may find a way to do it.


EDIT: I just realized I'm contributing to the hijacking of this thread, and I'd just like to say, I hope server side modding is a possibility, because mods like this could completely restructure this game to give expanded appeal for certain players. And what Syox is thinking about doing is easily possible, if seemingly difficult to do right.

Ahh, this is true, but really this is just the "simple math" I was referring to. (Though honestly, I had totally overlooked the integration aspect, whoops, that's the most important part for efficiency here)

Though, in the defense of the initial post, the primary places a modder would be working to mod would be the cost and integration fields, and the generation of the flow field from those two would remain relatively unchanged for the game to interact with. Plus ignoring the integration makes it easier to explain... Even though the integration part is what makes it possible, considering all the problems that have been pointed out with a rigid grid system.

So thanks for the link and clearing that up.

EDIT: Holy **** I sound like a total *** and I don't know how to fix it. I just realized you were actually on their team and this has like... Zero respect in it. But seriously, lots of respect man, sorry if this post was rude. And thank you for taking the time to help clear this up.

Do you really use distance too?
Looks more like costs without distance also even only calculating over the sides and not the corners.
But visualls can lie, only the source shows truth :twisted: .

I was allways referring to the integrated costs field, so shame on me for not ever using the right terms. As far as i can tell i dont want to edit the flowfield but the cost and maybe the integrated costs field(multigoal support). I used the term flowfield as synonym for the integrated costs field, because i thought you are only generating the vectors for each unit per step, so i simplified it to be one and the same. I will use proper terms from now on.

Btw: i really dont think distance stuff is usefull.

Ok i read the paper of continuum crowds.

The integration algorithm itself works exact as expected.
Multiple prioritized goals could be achieved with:
Every goal is a known.
All surrounding cells (N,E,S,W) of every goal are candidates.
The algorithm starts with the lowest value, continuing with the lowest of all bigger values.
One thing to assure here is. That no goal value is higher than the surrounding integrated cost values.

This could be achieved by the following constraint:
(Under the hypothesis of discrete integer cost with a minimum of 1 per cell)
Goal_value_i <= | goal_i_x - goal_j_x | + | goal_i_y - goal_j_y | for all i,j in 1,....., #goals; i =/= j
< if you want to have real local minima






The continuum crowds algorithm itself is probably not useable 1:1 as it has its flaws with inertia.
Well at least if you want to have inertia . Otherwise there is put a lot of thinking in it.

The distance field mentioned here is pretty much identical to thier integration field. It's just a difference in how it's explained - in game, there is never a seperate field containing "distance". It skips the middle step and just adds the distance straight on to the pre-existing cost field, if I understand correctly. Of course, it appears the team have used a phrase slightly more accurate (unless there are some changes I don't fully understand.

Also, it seems we have gained some new knowledge. There appears to be a seperate flowfield stage, which is a more literal stream of arrows, taking even less strain off individual units.

Though i am not sure if this is more optimal in cpu time...
Also considering the changeability of the flowfields.
I mean you do another full circle over the integrated costfield. wich is something like O(m*n) (m,n size of the array) instead to the O(4*n) (n == #units) to just check the integrated cost field for next direction, but i dont have the real code so thats alll just assuming. If the Flowfield is be used for several seconds it sure is faster, if its changing alot ... meh i dont know

after all Elijah will sure know


Though thats not the purpose of this thread, got carried away :lol:

Edit: think Elijah mentioned it in the livestream.
http://www.youtube.com/watch?feature=player_detailpage&v=5Qyl7h7D1Q8#t=3588s

Edit2: Well if you do it while integration. It should be pretty cheap. so forget my post about algorithmic costs above.

Every algorithm has problems when inertia is simulated for units (in their motion model) but not taken into account during path generation. Games usually don't do this because inertial constraints make the problem of finding the min-cost path *much* harder. It's where collision detection against other units and terrain has to come to the rescue, which can be done in many ways and is as important to gameplay and realism (for example a major reason for the "sliding" units in SupCom II was that its collision handling disregarded friction) as the pathfinding system itself.

Yeah i know. I meant to calculate the vectors on the current position only(not the whole flowfield per unit, but afterwards i realized that you can create the vetors while integrating over the costfield so no huge increase in computing costs there.

It depends, really. For example, using one unit, having no separate flowfield stage would take less memory, and be faster. You wouldn't need to precompute the arrows for every single spot on the field, only the 9 around the units at all times, and you would only need to store the position or the current known lowest value and it's position instead of storing an entire field of directions..

However, it doesn't scale well - imagine now you have 10,000 units. Every single one needs to do it's own calculation of what the cheapest pixel nearby is, hold several values in it's memory to store the x,y position and the value of the lowest number, and needs to do this every single time it moves just one pixel.

A lot more expensive than just doing one computation across a grid, then for the end flowfield just holding this grid taking up a memory size in bits of just "(x * y) * 3" (the 3 being 3 bits to hold 8 directions).

However, every time the cost changes, the flowfield needs updated (part of the reason it's all split into sectors). You can't just enable/disable a certain object giving out cost and expect the end result to work, as you need to also update this virtual stream of arrows.

However, it's worth it in the end - you must remember that PA has a unit goal number of 1 MILLION. Far more than ever attempted before in an RTS game, by several orders of magnitude. On that scale, saving just a small amount of memory per unit makes a pretty big impact.

Well easy solution: Start steering earlier. Should be no problem for the plains like we saw in PA. Harder to do in close streets though. Its adapting motion model to path.

You nailed it.
Also 4 bits afaik