rishabsingh3003
commented
4 years ago Another way to do this would be to uniformly divide the plane into a set number of N X N nodes. And then delete the nodes that are coinciding with obstacles.
(Red nodes are obstacle nodes, green nodes are the path taken, blue are the available nodes)
But that's a really bad way to approach this problem, and will never work out
Most graph bases algorithms (Djikstras, A* etc) require a set of nodes. Now the algorithm has already been designed and implemented, but how you assign nodes is extremely important. For reference: The algorithm must be fast enough to run(give the shortest path per bot) at least 4-5 times a second. *Applying Djisktra's on 40 nodes takes < 40 ms to run, applying it on 4040 nodes takes about 30 seconds to run (On my i7 processor).**
Therefore, a good scheme needs to be developed to mark the nodes on the plane(I.e node map). One good way to do this (inspiration taken from ArduPilot), is to mark the nodes in the following way:
To see the third point graphically:
Here "0" node corresponds to starting location of the bot "1" node corresponds to goal location Nodes "2" - "5" are margin nodes of the obstacle.
Therefore, the bot can travel from one node to node, as per the algorithm, and safely traverse through the obstacle.
Again, this map can be used for any of the "node" based shortest path algorithms. I would suggest we follow this but comment down below any changes that you think might benefit the project.