#Implementing Bi-Directional A* in C#
languid perch
the termination condition of my a* is wrong (maybe you can help me) but i can give u a advice to optimize
you are trying to sum up all distance of node from its parent until reaching start node of path which is an O(log(?,n)) operation
you may consider using a dictionary to store all visited nodes' f value and have a O(1) access also easier to debug
half apex
I havent looked at the code yet, I am waiting for a reply from @snow cedar to see if he has fixed it by now
Using a dictionary / hashset to store visited nodes is pretty much required though
Also, lil piece of advice @languid perch - implement the algorithm first, then optimize it. Sometimes optimization obfuscates the algorithm in such a way that it becoms hard to follow the code flow, which makes it a lot easier to make a mistake while implementing it
snow cedar
Oh hi ! I just came back home. Alright, so ive done a few adjustments to my code.
one of them being, i created a whole new class for pathfinding.
Me and ChatGPT were up all night trying to figure this one out hah. I had some issues with comparing two nodes with eachother. But it all got rightfully solved when i stopped comparing float distances and started comparing using manhattan distance and ints instead.
There is however something that is still wrong with the algorithm, where if the target tile is surrounded, the algorithm never stops
As you can see, i implemented both a normal A-star and a Bi-directional one in the code above
half apex
There is however something that is still wrong with the algorithm, where if the ...
This is a problem with pathfinding algorithms in general, often solved with a cut-off whenever a certain path length is reached e.g. your min-heaps best path is a length of 2x Euclidian.
snow cedar
Well, sure, but using the bidirectional search it should terminate as soon as all the queue from the target tile is empty
half apex
Another approach, which can be implemented only with bi directional a* is to stop whenever the openlist of any of the two searches becomes empty and no path has been found yet (there won't be a path because one is encased) but even in this case
Beat me to it ;)
half apex
I will give it a look, I scrolled through it but it's a lot of code x)
snow cedar
Im sorry :3
haha
It's looking alot more cleaner now than last night tho, let me tell you that
half apex
No worries I enjoy algorithms I'll have a look at it in an editor now
You can make it even cleaner if you would make a class which holds a specific search
And instead of a while loop invoke a step function from outside the class
Give me a couple of minutes and I'll type something up
half apex
I am not at all
snow cedar
No problem ^^
I came up with an alternative for my pathfinding in my game. Using a compute shader and a BFS search. Searching the whole frontier in pararell
half apex
Aha, do you still want me to look at your code or are you going to go with that?
snow cedar
oh nono, just having some alternatives in the bag
would still appreciate if you would look at my code 🙂
languid perch
i dont know what is compute shader means but i believe multithreading cant be applied to speed up the path finding process
since each time you enqueue/dequeue/check visited is critical section, nearly all steps in bfs are critical sections
snow cedar
i believe it would be possible as long as the enqueue and dequeue are atomic operations
half apex
@snow cedar
when talkin about the steps
re-use the logic that is used to perform a bfs
I am going to be honest with you, the code you send over has too many lines for me to reasonably find errors in
So i'd have to build a full copy of your project, and check it that way
snow cedar
So i'd have to build a full copy of your project, and check it that way
alright, well i dont think you wanna do that, its huge at this point.
languid perch
I am not sure whether enq deq is atomic or not, but even is yes,that means when enq/deq the os will block other threads from reading/writing into memory
half apex
I simplified it a little bit but this is really just to showcase how to do bidirectional a* while re-using
I dont think this benefits from multithreading :s
snow cedar
oh yea no, a-star does probably not benefit from multithreading
but a BFS search i think will.
snow cedar
https://pastebin.com/KdFZnYNp
oh, youre reusing the one directional a-star function in the bi-directional one. Why didnt i think of that haha
snow cedar
haha exactly!
half apex
Then you only need to add the logic where you check if the visisted sets overlap
snow cedar
oh holy smokes, you can also then calculate both ends at the same time in the while loop
Also, i asume this would allow for some easier debugging aswell. as i can step through the search manually
snow cedar
Hats off to you sir
half apex
And debug thati nstead
snow cedar
wait, why?
half apex
Also, you can problably remove lines 120-129
If oyu know the dearch works in one direction
it works in the other
and I personally find it hard to debug two traces at the same time
Ofc I didnt do all the work by the way, you still need to write the reversing script for the target-side (be sure to remove the duplicate node)
But I think I saw some code for that already
snow cedar
yea, its in there
snow cedar
haha right
i had several clues online while researching that that was the case. I just never cared to swap them around
half apex
Funtionally shouldn't matter though
snow cedar
Ill implement this and see what happens
question, whats the point of having {get; set;} when declaring a variable? would just omitting it be the exact same thing?
half apex
It would be same, but some programs (like unity) use reflection to look for getters and setters
and sometimes requires them to be there, or to be absent
I think they dont show up in the inspector if you add {get; set;}
but I'd have to check
I really just do it out of habit
snow cedar
okay
snow cedar
Hey HamCrank.
var neighbours = new List<SimpleNode>(); // this should be all of your neighbours
foreach (var n in neighbours)
{
if (Visisted.Contains(n))
{
continue;
}
float g = current.G + 1;
float h = n.Position.Distance(_target);
// If we found a faster way to get to this node, update it
if (Queue.Contains(n))
{
if (g < n.G)
{
n.G = g;
n.Parent = current;
}
}
else
{
// We haven't seen this node before, so add it to the queue
n.G = g;
n.H = h;
n.Parent = current;
Queue.Add(n);
}
}
in this piece of your code
when you update the neighbours values
doesnt that just update a new instance of a neighbour?
half apex
It does
thats an error
You should get that item from the queue and edit it there
that clause is entirely optional by the way
itll just sometimes find a better path
snow cedar
Aye. But should probably be in there :>
think im done with my conversion now.
I straight off copy pasted your SimpleNode code btw. Changed the values to ints rather than floats
public Node(Vector2Int position, int g, int h, Node? parent)
{
Position = position;
Parent = parent;
G = g;
H = h;
}
This is throwing a warning btw, because of the ? in the parameters
is node not nullable or what?
I kinda dont understand why its there tho. Isnt that supposed to do something special if the variable is null? cant remember
half apex
Marks the type as nullable
since C# 8.0 or maybe 7.0 microsoft tightened the rules on nullables, they used to all be nullable by default and now that is no longer the case i think
I was working in just a console app, not a unity project btw
Its really just concept code, I never ran it
snow cedar
public Tile targetTile
{
get { return targetTile; }
set { (sourceTile != null && targetTile != null) ? Status = PathFindingStatus.Ready : Status = PathFindingStatus.NotReady ; }
}
Is this wack?
Im kinda new to this whole {get;set;} thing
snow cedar
I believe the compare method is messed up
The compare method is based on F. which is fine, thats how we wanna sort it. But since its based on F im also not allowed to add two Nodes with the same F i think.
yea.. cause the Add() method of a SortedSet doesnt allow for duplicates and uses CompareTo() to both see if two things are the same and where they should be placed in the SortedSet.
If CompareTo() returns a 0 it doesnt add because they're considered the same.
snow cedar
Feel like im getting collisions in the hash function.. im not able to add stuff properly
half apex
Hm that's strange
Again I didn't test it but the hascode function should be fine
About the sorting, that's just unfortunate..
But it is going to happen that nodes will have the same F score
Probably going to have to resort to a custom implementation of a Pqueue :s
Or can just try the inplace Array.Sort method
snow cedar
think i fixed it actually
half apex
```cs
public Tile targetTile
{
get { return targetTile; }
s...
Don't make it too complex, it is better if you keep these methods simple
snow cedar
public int CompareTo(Node? other)
{
if(Position.x == other.Position.x && Position.y == other.Position.y)
{
return 0;
}
if (F > other.F)
{
return 1;
}
if (F < other.F)
{
return -1;
}
return 0;
}
wait actually, this wont fix anything. hah
half apex
Nope
snow cedar
it fixes a different issue
half apex
Reminder that the code I sent you was just to show you about the step() method really
snow cedar
ayes
really helpful. Im trying to rewrite it to suit my code
Almost there tho!
youre gonna laugh at my implementation atm tho
its so...spaghetti
On a positive note, the game doesnt freeze anymore now. Cause im only doing one step in the pathfinding each frame. hah.
Downside, there's a bit of delay between clicking on a tile and it finding its way there. hah.
No problem tho. Ill fix that later.
Oh right. another issue. I had to remove the updating of previous nodes clause.
It acted super strange when i tried to retrieve an item from the SortedSet
as in, i was debugging it and it behaved as if it used assembly languages rjmp to a earlier point in the program counter.
half apex
That is strange
Wait actually I read about this in the docs
You can't edit items in sorted sets
snow cedar
! what now
half apex
You gotta remove and then re add them
half apex
Scroll past the example
There's also a sorted list by the way
Maybe that one does allow duplicate keys?
snow cedar
i mean, maybe
but i feel like a hashtable is quicker no?
as i think sortedset is
or wait, is it?
im down the rabbit hole now. i dont know which way is up or down. 😅
half apex
Just looked at sorted list, it also doesn't support duplicate keys
For now you might honestly be better off just using Array.Sort or just write your own MinBy() method real quick
snow cedar
okay this is super wierd..
public int CompareTo(Node? other)
{
if(Position.x == other.Position.x && Position.y == other.Position.y)
return 0;
//If the nodes arent the same, sort by using the F value.
if (F > other.F)
return 1;
if (F < other.F)
return -1;
//If both nodes have the same F value, sort by using the H value instead.
if(H > other.H)
return 1;
if(H <= other.H)
return -1;
return 0;
}
public int CompareTo(Node? other)
{
if (Position.x != other.Position.x && Position.y != other.Position.y)
{
//If the nodes arent the same, sort by using the F value.
if (F > other.F)
return 1;
if (F < other.F)
return -1;
//If both nodes have the same F value, sort by using the H value instead.
if (H > other.H)
return 1;
if (H <= other.H)
return -1;
}
return 0;
}
Why does the first one work, but not the second one??, i feel like they should act exactly the same
languid perch
Boolean algebra
Not (a and b) = not a or not b
Other word: in case 2 , either two nodes in the same column or same row then just return 0
languid perch
You just turn && to || then it should work
snow cedar
Had a very interesting night. Thanks for all the help. Unfortunatly i wont be able to continue working on the algorithm until tomorrow afternoon.
half apex
All good chief, if you enjoy stuff like this I want to recommend adventofcode, it's an advent calender with coding puzzles (December 1-25) and some of the solutions require stuff like this, keeps me sharp
snow cedar
I can happily inform you that while the a* algorithm more or less works flawlessly, ive found that it is somewhat taxing on the CPU in my game BUT ive found a solution. The navmesh.
Feels like im getting closer and closer to unitys built in Navigation though
A fun project nonetheless tho
half apex
There's probably a ton of different ways you can speed it up
Dont know if you are already using a priority queue
but that could help
And I made an error in my script where you overwrite the parent if the current route is fast, dont check the open list (or Pqueue in this case) as thats really slow, it results in a complete enumeration of the datastructure to look for said element, do it on the hashset instead