danger_factor - what is this exactly?

[KWo]

Originally Posted by sPlOrYgOn

yea I guess it's something like that.

OK - Now need only ask PMB why the default is 800 and what exactly is meaning this 800, because this is still not clear for me. Probably he made some tests and after these tests he gave this value as default. I' ll wait.

[sPlOrYgOn]

well he probably thought 800 was a good value...
I think so too..
I've played de_dust for about an hour and saw after about 5 or so bots die in one area the rest of the living bots start running the other way
this is what happen..
there are 30 bots..
15 T, the whole team, goes through underpass.
5 of them get killed and the other 10 start running back up the stairs and going to hall..
at least it works pretty well...

[Pierre-Marie Baty]

It would be meaningless to try to explain what this value of 800 represents and to define a scale with a minimal and maximal value, because the progression is logarithmic. For example, there is quasi no difference at all in practice between 800 and 1000 but there is a great deal of difference between 200 and 400. The danger factor rises very fast in the low values, and slower and slower the more high you get.

This value must be strictly positive (> 0).

It is tightly related to how the pathfinder works. In algorithmic terms it's simply the cost factor.

An A* pathfinder works exactly like the guy who pours a glass of water. The "water" starts to spread from the current waypoint in all directions and stops immediately when the goal waypoint is found. Each time the "water" (i.e, the search) advances to a new waypoint, it adds something to the cost it takes to go to this waypoint. And in order to direct the search towards the goal, the search also stores the estimated cost it thinks it WOULD take to get from there to the destination waypoint. The final cost, which determines whether the pathfinder likes or dislikes this waypoint, is then as follows:
waypoint cost = actual cost to get there + estimated remaining cost it would take from there to the goal.
The estimated cost is called the pathfinder heuristic. It's simply an estimation based on the remaining distance. In our water spreading example, it works as if the map was "inclined" towards the goal when you start to pour the water.

How fast the water advances in a certain direction is determined by the cost it takes to get to the waypoint the water (search) has currently reached. When someone in the bot's team is killed at a particular waypoint, this waypoint is weightened with the damage taken and the nearby waypoints are weightened a bit too (but less). The danger_factor is how much this waypoint weight will be multiplied by in computing the cost to go to this waypoint.

For example if at a particular waypoint a guy died by losing 40 health in a row, this waypoint's cost during a pathfinding session for a bot in his team will be:
cost = sum of all the weights for all the waypoints that led to this one + (this waypoint's weight * danger_factor)
that is to say,
cost = sum of the previous weights + 40 * 800
that is to say that the pathfinder will dislike this waypoint very much, and the "water" will take a LONG time spreading from this waypoint to the next one during the search. In fact the same water will be likely to touch the goal faster by another route than it will take to move from this waypoint to the next one. If the other route is VERY long (or very expensive too), then despite the very high value for this waypoint the search will have advanced and continued to the goal faster than the time it took to travel all the way by the other route, but what happens most of the time, is that when the search "forces" to advance after this waypoint, meanwhile it expands everywhere else and another route is discovered before the costy waypoint is passed.

I have uploaded a small utility that was written by Brian Stout for an article he did for GamaSutra that will make you understand how all the different pathfinding algorithms work. I recommend everyone to give it a try.
http://filebase.bots-united.com/pafi...on=file&id=106

[KWo]

Thanks a lot for this explanation. I hope I will more understand from this tomorrow, because now - after my 6h tests with botskill parameters - You can see results here: http://forums.bots-united.com/showpo...1&postcount=15

- I 'm simply too much tired to try understand this explanation at this time (2:45AM).

Once again - thanks a lot PMB.

EDIT

OK - I used a dictionary and I hope now I understood all.

You said :

When someone in the bot's team is killed at a particular waypoint, this waypoint is weightened with the damage taken and the nearby waypoints are weightened a bit too (but less).

This means for me some strange situation. If there is a place on the map with a some waypoint and near it "fire in the hole" was, and each from 5 bots from one team took 99 damages , but no one was killed, the cost of this waypoint is not changed. But the same waypoint, the same situation - each 5 bots took 20 damages and everyone was killed - the cost of this waypoint =5*20*danger_factor. This is a little bit distressing.

I hope this alghoritm can calculate the same way on these two examples at my attachement. Imagine, that there is a map 100m x 100m and at first You have waypoints every 10m (10wp x 10wp), at second (the same range) You have waypoints every 16.67m (6wp x 6wp). S is a started waypoint , G is a goal waypoint, K is a waypoint where the bot was killed (the same damage on both maps), A is a wypoint nearby K, W is a wypoint not affected by K. In both situation I set danger_factor at the same value.
I hope that the distance beetwen two waypoints (between A and K) is affected to how much less the waypoint nearby are weightened, too. This should be logarithmic , too (I hope). Because if not - if the same "less" value have at both maps (but the distance beetwen 2 wp is longer at the second map) - this danger_factor can't be constant at both these maps to give the same result (the same path calculated to go). In this case the danger_factor should be depanding of "density" of waypoints on the map. The red line I showed the way for bots after taking "a kill" at K point. The blue - I think is the optimal way (between to A) and both way from S to G (across only the red lines and across the red and the blue) should have the same cost like this red - in this case probably the danger_factor is optimal. But it's depanding of people - how big area they want to avoid after killing bot. This should be showed at the table - danger factor aaa, damage 100 = distance to avoid bbb meters. In this case all will be clear to all people wanting use/change this parameter (danger_factor).

Once again thanks a lot of for explanation.

/EDIT

[KWo]

Sorry for double posting, but this "edit" function prefered by all here doesn't change the date and time stample of the post, so nobody can see I wrote something more.

[@$3.1415rin]

the water comparision is only true for water which is somehow attracted by the goal otherwise it'd be BFS

on http://www.lampel.net/johannes/joebo...XPDoc-beta.pdf on page 13 you can also find a short description of A*. but for further information, check the links at botman's site or maybe even those at gamedev.net

[Huntkillaz]

Originally Posted by KWo

Sorry for double posting, but this "edit" function prefered by all here doesn't change the date and time stample of the post, so nobody can see I wrote something more.

actually if u write

edit:


and that means what follows was edited part if it's in the mid just use like quote

edit:
hi
/edit


and even the the post date n stuff don't change atthe botttom of the post it says

'last edited by kwo on blah date blah time' so ppl will know and there's no need to post..double see (down here \/ )

[>BKA< T Wrecks]

Originally Posted by Huntkillaz

actually if u write
edit:
hi
/edit
and even the the post date n stuff don't change atthe botttom of the post it says
'last edited by kwo on blah date blah time' so ppl will know and there's no need to post..double see (down here \/ )

Yes, that's true. But will the thread / forum be marked as having a new post inside? I think that was what KWo was getting at.
If nobody posts anything new in the "common questions" forum, and only KWo edits his last post, will I see this yellow symbol next to the "common questions" forum that tells me: "hey, there's a new post in here"?

Ok, now I
EDIT
my post... just read your stuff, KWo, and I think this time it's ME who's too tired . Anyway, I think this mathematic example is fine, but most waypoint systems on real maps are far more complicated. Besides, on a real map there is not necessarily a connection between two waypoints that are theoretically close enough to be connected.
But in general, I agree with two of your main arguments:
a) that in an ideal case, it would not be a bot / player death (it could have been a bot with just 3 HP left) that causes a higher danger value, but the inflicted damage measured in hit points - whether it kills someone or not. Maybe even stronger if it has killed someone.
b) that "nearby waypoints" are not defined as waypoints that are one connection away (no matter if this connection is 100 or 250 units long), but as waypoints which are inside a circle around the center waypoint (where the danger was caused), with the diametre of the circle depending on the inflicted damage - the higher the damage, the bigger the circle.

Ok, but let's leave theory aside for a moment: (1) the waypoint matrix is not two-dimensional but three-dimensional, (2) there are obstacles like solid walls or (think of the 3 dimensions!) floors and ceilings inbetween, and (3) it's all VERY dynamic. It would be a hell to calculate all this shit AND take into consideration if the "danger radius" is blocked by a solid obstacle etc. etc.
After all, the main purpose of this function is to get bots to use different routes, and I think that works fine the way it is. And if I get a sufficient result with a not-so-exact calculation, I don't think you have to break a leg to think of a super-accurate calculation that will eventually lead to a result that's equally sufficient, but not noticeably better. Well, just my opinion, of course. 9_9