Hello everyone,

I have a problem which is difficult to solve.

So, i have 30 units waiting for orders. When i move them, i make a unique route from the first unit in the list (by the for loop), when the others units finds one node from the main path, the next node arent't calculated but simply added from the main path's list. It decrease greatly the calculation process time.

The vehicles which have the higest ID has the priority, except if another vehicle is front of it, in this case the higher must wait until the path clean.

It appears i'm trapped myself in a serious problem. I have seen somewhere i need to make an algorythm named "floaking algorythm" to solve that, but i'm not sure if that must be in the astar system or if is internal of each vehicles and if this is the correct thing i need to.

When i said "be in the astar system", that's means i was forced to make my own astar algorythm, because the current godot astar node isn't suited for a large cells numbers for generated map.

What can you advise me ?


  • Megalomaniak replied to this.
  • That's it, I made it !

    So, when it use Bresenham to determine the type of way (classic or astar), if is it astar, i must check what is the closest astar point at the current Bresenham list's point. If the astar node distance is too far in comparison of the position distance of the unit, to the mouse position, so we need to check another node. When this node founded and the first is more closer, we make the path from this node, i "change" the closest node to choice if you want.

    But if we do a move in other direction, this doesn't works, except if we add as condition we found a non-passable cell too soon, in this case, we use the "normal" closest node. And the result is great ! Some of units goes directly to the mouse position, some others make a little "deviation" but no one blocks the others.

    TwistedMind floaking algorythm

    I'm not aware of what floaking means, did you mean flocking?

    TwistedMind but i'm not sure if that must be in the astar system or if is internal of each vehicles and if this is the correct thing i need to.

    if it's something like a racing game then I'd think individual makes more sense, you want the entity to try and follow it's ideal path through the 'track' lets say, and if it finds a moving obstacle on the path then it might stick to just following on it's tail until the blocker should move out of the way on the ideal path thus allowing the entity to speed up and potentially overtake/pass by whatever was blocking it's ideal path.

    That's not necessarily the only way to solve it but conceptually might be the simplest way to go.

    But then you mention A* and I'm not sure pure A* is commonly even used in racing games...

    Yes, flocking is the correct word.

    No, this is a RTS game. The velocity of each entities doesn't change, i just need to avoid stuck situation.

    Here my logic: the unit setup has 3 raycast sensors. If at least one of them collide another unit, something must be done (wait or take priority).

    Case 1 = if unit 2 detect an ally which go front of it, unit 1 must "shift" to another direction for the following cell and take back the path normally.

    Case 2 = if an ally goes to the same direction of the unit, someone must take priority and the other must stop.

    Case 3 = if an unit collide an ally and it is in front of it, wait, event if his id is higher.

    In practice:

    func checkCol(rayVar):
    # srcScript = the unit who detect another one
    
    	var rayDirect = rayVar.get_collider().get_parent()
    
    	if rayDirect.UnitPath.empty() == false and srcScript.id < rayDirect.id and\
    	srcScript.UnitPath[srcScript.step] == rayDirect.UnitPath[rayDirect.step] or\
    	rayDirect.modeConstruction:
    		srcScript.delayPushNeigbor.start(0.5)
    		srcScript.set_physics_process(false)
    
    if srcScript.rayPushDir.is_colliding():
    	var rayDirect = srcScript.rayPushDir.get_collider().get_parent()
    				
    	if rayDirect.UnitPath.empty():
    	else:
    		if rayDirect.modeConstruction:
    			srcScript.delayPushNeigbor.start(0.5)
    			srcScript.set_physics_process(false)
    					
    		elif srcScript.id < rayDirect.id:
    			var dirDict = {'horizontal':Vector2(1, 0),
    					     'vertical':Vector2(0, 1),
    						'diagonal':Vector2(1, 1)
    						}
    						
    			var normOldangle = srcScript.oldAngle.normalized().round()
    			var normOldangleUnit = rayDirect.oldAngle.normalized().round()
    						
    			if normOldangle == dirDict['horizontal'] and normOldangleUnit == -dirDict['horizontal'] or\
    			normOldangle == -dirDict['horizontal'] and normOldangleUnit == dirDict['horizontal']:
    				modDirection(dirDict['vertical'])
    
    			elif normOldangle == -dirDict['vertical'] and normOldangleUnit == dirDict['vertical'] or\
    			normOldangle == dirDict['vertical'] and normOldangleUnit == dirDict['vertical'] or\
    			normOldangle == dirDict['diagonal'] and normOldangleUnit == -dirDict['diagonal'] or\
    			normOldangle == -dirDict['diagonal'] and normOldangleUnit == dirDict['diagonal'] or\
    			normOldangle == Vector2(1, -1) and normOldangleUnit == Vector2(-1, 1) or\
    			normOldangle == Vector2(-1, 1) and normOldangleUnit == Vector2(1, -1):
    			modDirection(dirDict['horizontal'])
    							
    			elif not srcScript.modeConstruction:
    				srcScript.delayPushNeigbor.start(0.5)
    				srcScript.set_physics_process(false)
    			else:
    			srcScript.delayPushNeigbor.start(0.5)
    			srcScript.set_physics_process(false)
    			
    		elif rayL.is_colliding():
    			checkCol(rayL)
    
    		elif rayR.is_colliding():
    			checkCol(rayR)

    And here the code when the unit stopped waiting end:

    if rayPushDir.is_colliding():
    		var rayDirect = rayPushDir.get_collider().get_parent()
    		
    		if rayDirect.UnitPath.empty():
    			rayDirect.physxProc.pushAway(rayDirect) # physxProc = another script which containt condition code upper
    		
    		elif rayDirect.is_processing():
    			delayPushNeigbor.stop()
    			configFrame() # orient vehicle then advance
    	else:
    		if rayPushDirL.is_colliding():
    			var rayDirect = rayPushDirL.get_collider().get_parent()
    			
    			if rayDirect.id < id or rayDirect.UnitPath.empty():
    				delayPushNeigbor.stop()
    				configFrame()
    			
    			elif rayDirect.id > id and not rayDirect.is_processing():
    				delayPushNeigbor.stop()
    				configFrame()
    		
    		elif rayPushDirR.is_colliding():
    			var rayDirect = rayPushDirR.get_collider().get_parent()
    			
    			if rayDirect.id < id or rayDirect.UnitPath.empty():
    				delayPushNeigbor.stop()
    				configFrame()
    			
    			elif rayDirect.id > id and not rayDirect.is_processing():
    				delayPushNeigbor.stop()
    				configFrame()
    		else:
    			delayPushNeigbor.stop()
    			configFrame()

    Flocking algorithm is what i'm looking for i'm sure now. I will probably need it for further purposes because when i will assign my units as group 1 or another group (1 -> 10), i will want a basic formation but only if the units have a group assigned.

    But the task seems to be very difficult because my units moves cell by cells, not like a game as Age Of Empires 1-2 or similar. The examples i have found on Godot library doesn't suit for my case...

    If it's any consolation, I'm not doing cell by cell movement with my pathfinding and I'm trying to find out how to implement things like building placement cleanly so that the paths calculate automatically around the obstacles when they're placed and it's a struggle getting it to work. I think some collaboration might be in order just to help out the noobs as well who will inevitably be running into these problems while developing any kind of RTS or RPG game that relies on click to move pathfinding. I was thinking like you that I've possibly been misinterpreting what TileMaps are for and if I shouldn't be relying on a custom A* Algorithm of some kind that detects all of this properly.

    Isometric/2D RTS'/RPGs are my favourite genre I've realised when looking at what I actually play and there are not a lot of them out there, it would be great if the Godot community could make it easier overall to develop them by whipping up some examples, so far I've managed to get box selection and general movement up to date and working fine and even build placement mechanics but the pathfinding is an issue.

    Should actually upload a more up to date video now I think about it, I've added stuff lol but the pathfinding has been annoying me. Like you when I move units they simply get stuck on the obstacles and don't calculate around.

    I mean I wonder if we're possibly being too fussy or expecting Godot to do something it can't? I keep thinking like I've mentioned previously if this isn't a misinterpretation of what the TileMap and navmesh obstacles can do. There's plenty of old RTS/RPGs that behave this way and you just click around the buildings as a player, but then again with modern software surely it shouldn't be so difficult to have the agents calculate around these obstacles properly?

    By the way @TwistedMind Looking at your older examples of the vehicles getting stuck, I suspect your path is calculating fine but the agents are potentially just defaulting to their dumb behaviour and trying to go straight to the point and not detecting the water tiles you have there, I think I've got the exact same problem.

    Have you tried increasing the radius of the agents?

    Lethn

    For my case, this isn't the terrain's obstacles which anoy me, it's the vehicles themselve, especially when a "priority traffic" must be done (like cars on a crossroads). I think the astar isn't the problem, it's how to units avoid their neighbors and move to the same direction.

    The astar algorithm work like water in a maze. The best solution i have found, is to catch one path of the units group and use it as common route for eatch others. I'm sure Godot is able to do that, this is a question of coding. Larger old RTS games use fixed map but some use procedural from a noise texture.

    ...behaviour and trying to go straight to the point and not detecting the water tiles you have there...

    The water tiles are detected as unreachable in my astar system, only for land vehicle. In my previous prototype, each units's path is calculated by astar but if i have 30 units, the game freeze some seconds, so using common and unique route for the group avoid complex calculations for the same cells, according tho the initial position of units and that give me higer performances.

    What radius do you talking about ? You mean Neightbors cells while defining the path ?

    The agents have a built in avoidance radius which may be worth playing with, you could for example make the vehicles have a fairly big radius and it might partially cure the problem.

    I'm note sure to understand. To make the path, i use the tilemap'ss cell coordinate and i convert to world for the final path so in don't understand how the navAgent2D node can solve my problem.

    Oh I hadn't realised that you weren't using Godot's built in agent system, that explains a lot, you may want to try it to see if you get a different result.

    I need to search somes informations about this 2d navmesh.

    Okay, so the nav2D node seems to be not suitable for my problem:

    The navigation2D node, navigation agent2D and other nodes linked to a navmesh, cannot be applyed to my case because my map is generated, not make by hand (even if i place tiles myself). This is because the time to make the navmesh will be very too long (and maybe too complicated, map aren't the same for each game sessions).

    So i will need, like the astar system, to make my own flocking system, to avoid this. I understand the basis and i'm close to the solution. The questions remains are:

    • How to designate the "master" of the group if they move freely;
    • If the units are assigned to group X, who is the leader;
    • If one of the member has and unreachable tile, how to reset a valid cell.

    From the original game inspires me, the point 1 still fuzzy, point 2 i know is the middle of the list or the highest ranked units must be as master and the point 3 is a little fuzzy too but maybe a link with the direction of the master.

    In fact, this is like moving in (military) formation, in all circonstances.

    • xyz replied to this.

      TwistedMind I don't think you actually need flocking. I'd just calculate A* path for every unit individually, let them each go on its own path and devise some type of continual separation scheme whenever an overlap occurs.

        xyz for long distance, calculating A* for each units take too long, and freeze the game a little moment. That's why i take the first unit's path as common path. When the others units has one similar path step to the common point, thats mean it will take the same point for the rest.

        ...devise some type of continual separation scheme...

        Can you explain ?

        • xyz replied to this.

          TwistedMind for long distance, calculating A* for each units take too long, and freeze the game a little moment

          You should optimize the A* structure then and/or decouple the calculation from the frame update by delegating it to a worker thread.

          TwistedMind Can you explain ?

          Continually check every pair of units against each other during the movement and separate them if they overlap.

          Continually check every pair of units against each other during the movement and separate them if they overlap.

          This is not the flocking/boid algorithm supposed to do ? What his goal them ?

          • xyz replied to this.