UPBGE Flow field and pathfinding

hello everyone has anyone done an implementation of a flow field or vector fields to navigate units in UPBGE through a component? and what was its performance compared to other pathfinding methods-A*(stars), Navmesh?

in general, I tried to make the flow field without using dictionaries and writing to a nested list while the path search works for all units, but not for each one individually-maybe someone more experienced will have advice? I’ll listen with interest. I will attach a file with my tests :slightly_smiling_face:Potencial_Field_Test.blend (248.3 KB)

A* works fine, depending on what you can comeup/create with. If you use a* just to create a path from A to B and then use the path on 100 objects, then it’s not heavy at all(A*), but if you use 100 objects that each calculate their own path, then that will take a second or 2 to calculate (if all done on same frame) depends on the sort of a* you use.

1 Like

Hello Mr. Cotaks! thank you for your answer! A* I looked, and I think that it is not really suitable for large spaces and large numbers of units in groups - as can simultaneously calculate the diagonal way to the finish line and to the right and to the left of the agent, and agents 7-9 load the game when you start calculating the trip again, there is an algorithm of the jump points - modification A* but I will not write - so I decided to try the flow field it was used in supreme commander and planetary annihilation for navigation of large numbers of units - there was calculated the way across the map(the region if map is large) but not every unit but a single object and passed to the execution units
so I decided to see if there’s a similar implementation in BGE UPBGE or how can implement similar behavior. sorry my english is very bad

the very basic way would be something like this:

path = A*

if path:
    for obj in own.scene.objects:
        obj['path'] = path

I didn’t quite understand, but what about the checks for U-shaped obstacles and T-shaped obstacles? or is it part of your code? i just do not understand the principle of operation, I just run a check at the neighbors of the finish cell and gradually add weight to the cells - then the unit moving from a large weight of cells comes to the smallest

Well if you use A* (seems you use based on breath first search). Then the calculations already keeps U and T shapes in mind. Because of the lower number of neighbours(so only one possible/shortest route is calculated).

But, you do work with a grid, so when you manually place(or spawning) those U and T shaped objects, you just disable the grid lookup for the grid tiles below the U/T shaped objects

My example is just to distribute 1 route to all the objects that needs to use that route.

I think I understand you - it’s like calculating the path across the entire map but not by all agents at once - but by one object-either a empty simulating the player, or a empty simulating artificial intelligence and passing the calculated path to all active agents who should start moving - am I right? or I again did not understand something:) PS happy new year to you

Yes indeed.

And if the agents are not on the grid, or on an other position then you could simply grab closest position from your list and activate the navigation from there. So even when agents aren’t walking close to the “route” you can still use that route to be used as the path.

Thanks, same to you!

Hmmm very interesting, I’m now trying to rewrite the test that I added earlier to use the dictionary to look up the next cell I want to make a dictionary key will be the number of cells from large values to small, and the value of the cells themselves in the scene, either do it using Numpy and matrix - just this is my first attempt to write a path finding without navmesh and ask nowhere - in Russia bge and upbge not popular and difficult to find information on such topics as the search path

Hello mr.Cotaks! Can I ask you for a hint? I redid my first pathfinding and everything works fine on waypoints but when the first agent is on the way and I select the second one and assign it a different target the first agent starts following to the second agent’s target ignoring its first target and I can’t figure out why it does this FlowField_Test_V4.blend (153.3 KB) I think there is an overwriting of the map which is a dictionary but I don’t understand why the agent writes the map only if it is selected and the player has set a target for it on the map with the mouse button :slightly_smiling_face:

map      = {}

is outside of a function, this means it runs in script mode. This in turn means that that piece of code only get run once then the script forgets about it. So this then means it’s either 1 object that can use it or all objects will use it as the same value, because it can’t get ‘updated’.

So map should be within a function or in the object itself as a property. Where a property in this case would be best solution, this way you can update the objects map itself per object.

Thus:

import blabla
map = []

def something():
    pass

Means it get run 1 time only per script call

def goodway():
    #python controller on agents calls let's say script.goodway
    map ={}
    #now map is used per object instead of per 1 or all at same time
1 Like

Wow, I didn’t know this, thank you for your answer, I didn’t know what this behavior of agents was related to-so i need to create a map inside the body of a class or function and then fill it with vector positions and return it to perform the movement :smiley: :+1:

Yes.

Also a few pointers

you using if states checking for conditions, while the property can only be one condition at the same time you should use elif after the first if statement.

if a == b:
    #tadaa
elif a == c:
    #if a != b then we go to this check to check if it is c
elif a == d:
    # rinse repeat

for ray’s you don’t have to fill in all the values

rayCast(to,from,distance)

would be more then enough

Good to see someone tackling pathfinding, and it works haha didn’t expect that when i looked at your code.

Keep it up, nice work, but don’t overuse it because the way you build it, it’s gonna be very resource expensive, if used on a lot at the same time.

:slightly_smiling_face: thank you again for your help, this is my first experience in writing pathfinding for BGE and RTS I will take your advice into account, if you do not mind I will show you tomorrow the screenshots for which game I am doing this pathfinding

Sure would be nice to see.

Also i’ll check if i can upload my a* pathfinding based on breadth first search. Maybe it can be used to by you or others.

Here it is, maybe it can be of use for you maybe not.

Anyway:

1 Like

Thank you for such a great example - I will study it and hope it helps for my project :smiley: :+1:


these are some of the units for my project - if you played dune battle for arrakis on the sega mega drive console, you will recognize these units, in fact I have already implemented the construction of buildings and their placement as in the original, made a fictitious extraction of spice-harvesters pass through buildings this is a temporary bug left to do the path search and behavior of military units and a project template will be ready through which you can create different missions for different factions.I will try on the weekend to put at least that part in which there is a construction of buildings in the topic of projects so as not to violate the rules of the site and be sure to share with you a link maybe you will like it and it will be interesting :slightly_smiling_face:

They look great.
Yes i know dune, in fact played all versions haha, waiting for the movie at end of the year.

keep it up! And indeed the work and progress topic is ideal for it.