Add a New Comment Rich Markup
2.3: Gradient maps are recalculated from scratch.
efficient to reuse the old gradient maps and only update the changes. The problems are vanishing sources and newly added obstacles, since they might spawn fields whose old gradient values were higher then their new would be. And this case we can't handle during gradient computation. Solution: We comb through the necessary parts of the gradient map twice: 1. we erase the gradient values that are too large and remember the fields that border this region. Here we avoid removing much too much by observing that, if field A has higher gradient as field B, then field B had no influence on field A's gradient value - or B was an obstacle. If it was an obstacle, we eventually encounter a proper source which will propagate the gradient to the former obstacle B. 2. we run a modified updateGlobalGradient using the sources that were added since the last turn and the remembered fields.
Gradients are the background of glob2 pathfinding. They are extremely efficient, but their computation nevertheless consumes a lot of cpu. A simple algorithm initializes every field with a starting gradient value which depends on the field and the type of gradient the algorithm is calculating. Then the algorithm takes one source and tries to improve every field adjacent to it. All improved field become sources - the old source ceases to be a source. Now we go to the next source. The sources list is managed by a queue. The increased field's gradient value is one less than that of the field which increased them. We have three general ideas on how to improve that: 1. Using the special geometry of glob2 (sup norm => circles in glob2 are squares): 1.1: We only make improved fields new sources, if we have too. This is based on an observation of Simon. If we have 3 fields immediately above each other and the two outer fields are (or were) sources, then the one in the middle does not have to become a source. Same for 3 horizontal aligned (Try this for yourself)
chess board. Check if this increases the source saving much. 1.2: We cluster the fields on the wave front on which the gradient propagates into lines. Thereby we save some checks and use memory (cache) in a better way.
will not be joined again by the algorithm. I want to check if it a more fancy line joining would increase line length much. (the average right now is between 2 - 3 fields). To check it, I propose to use a priority queue instead of a queue (larger gradient and smaller y-coordinate, x-coordinate => higer priority). Then measure the average line length.
2. New framework: Right now we do too much recalculation. Luckily we found a way to get rid of some: 2.1: Each team has its own forbidden areas. There are usually only few of them, but their effect is, that we have to calculate every gradient (not only forbidden gradients) for each team.
forbidden if it is forbidden for at least one team. Then copy this gradient and improve it for every team. We would do this by correcting the wrongly forbidden fields for a team. Then check the maximum gradient value of all adjacent fields and if necessary reset the value for the wrongly forbidden field and make it a source. At last: call the ordinary algorithm again with these sources. 2.2: Globs that can swim use other gradient maps than those who can't:
3: We don't need (correct) gradients all the time: (This is already implemented I don't know of any plans to improve it.) (4: I had an idea to use the direction in which the wave front propagates, but the overhead was to much.)
(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)
Attach Files: Comment:
No files currently attached
Depends on the following items: None found
Items that depend on this one: None found
There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.
Only logged-in users can vote.
Please enter the title of George Orwell's famous dystopian book (it's a date):
Copyright © 2023 Free Software Foundation, Inc. Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved. The Levitating, Meditating, Flute-playing Gnu logo is a GNU GPL'ed image provided by the Nevrax Design Team. Source Code
Powered by Savane 3.12