Hi evvvverybody,
I would like to make a Dijkstra algorithm plugin for in v4 in order to control a robot movement.
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
This algortihm is iterative and it can take time to find the shortest path of a graph.
I just didn’t understand how vvvv will react? Is the frame rate will become really slow ?
As I’m a beginner, I didn’t imagine the dificulties I’ll meet, so if you have any advice I’m interested…
Thank’s by advance for your help.
Hi welcome.
I think u7angel made a pathfinder plugin for vvvv, using a different algorithm. Although looking on his userpage I can’t find it.
Thank you for your quick reply,
I also find a message on the forum concerning A* algorithm, but I really want to use Dijkstra (or really similar algorithm) because of many reasons but I will take time to explain !
I had look too on u7angle userpage but nothing…
we developed an A* plugin, its kind of “not easy to use” right now but if someone needs A* i can help via skype.
if you want Dijkstra then A* could do the same but far from being efficient.
there is a lot of Dijkstra code in the web, should be easy to find. the problem is, you need to program a map editor to feed the algorithm. some editor with the possibility to set connections between points,calculating distances and save this into a list. i guess that takes longer than implementing the Dijkstra code.
concerning the framerate of vvvv, i guess the algorithm does so little work, it should not interfere with vvvv. well, depends on the size the network of course. but as you need to create the network, i guess its not that big !?
it just so happens, that i am programming on graph plugins atm, i am using QuickGraph which has all the algorithms one needs. making an additional node for the Dijkstra is a no brainer… what would be the output of the node for your application? what kind of graph do you use?
That’s cool I’m not alone ! Thanks a lot for your nice help
I had a look on the link but I dont really understand what is provide exactly by the QuickGraph library and how you use it in your plugin, but to explain in a simple way;
The node I dream every night is a node wich as 4 input;
And just one output;
Which give a liste of slices containing the path !
For my project, the table which contain the graph will be in a Mysql data base, so I’ll be able to modify it with different applications (android app and web browser) and it’s easy to access with v4.
(Sorry the picture it’s in french)
Makes sense to me, my a* plugin works pretty similar although u dont need the bang… calculation can happen on input change. lets see if tonfilm does it this way.
@tebjan, how do you plan to implement a*, we used a bitmap for the map data…you can feed a* easily with an insane amount of data which cant be routed inside vvvv as a spread. that kills performance instantly. i can only think of loading a text file or similar.
Ok, it’s the same for me with a real time calculation, I was just thinking to put a bang to optimise the performance.
If one of your functions are slower then others and you don’t want to slow whole mainloop you can just create new thread for this function. http://msdn.microsoft.com/en-us/library/aa645740(v=vs.71).aspx
yes, input would be graph, and start/end vertex. output the list of vertices of the path and a bin size pin.
how you populate your graph is another thing. for now there is a node CreateGraph which takes a list of edges. if you have a database you can use the database nodes or just write your own CreateGraph node, like in u7angel’s case.
i haven’t thought about vast amount of data… its more a basic vvvv node set to work with graphs. but as it uses QuickGraph and the data types from it, you can very easily add your own custom nodes.
Thanks alg for your advice.
Tonfilm, I agree with you, the question of how I create the graph is a different question.
So I’ll explain a bit in detail. My robot will move on a fixed network of tracks. This network will be represented in a mysql database by a table like I show you above. But thanks to a web interface (on smartphone or computer) the user will have the possibility to add some new edges on the networks to create a robot stop where they want to.
So to answer the question ;
I’ll create the fixed graph by hand. It’s not so huge graph, I just need to write a table twice bigger than the one above.
And the graph will be populate by the web appplication just by adding lines in the Mysql database.
When a modification is done in the database, vvvv read it and for the next path calculation it will include the new edges define by user.
NB:
I’m not sure to answer correctly your question… sorry if not
I didnt find the CreateGraph node in v4?
I’m not sure to understand the plugin you are working on… Is it a plugin based on QuickGraph library which will include differents node for path calcultation One for A*, One for Dijkstra…and a CreateGraph node ?
Thanks again.
ok tebjan, good to know…
will it be part of the next addon pack ? looking forward to it :)
yes, will be several nodes for different graph functionality. the nodes are in the making right now. they will be available soon. maybe with the next release.
you could join the irc if you want to be an alpha tester.
Hi,
What can I say ? It’s just magic ! I’m really impatient for the next release now !
See you on irc and thanks a lot.
haven’t seen you on irc lately. but i got the Dijkstra node working. check in to irc and have it tested, if you like.
looks awesome !
maybe useful too for vector laser shortest-path drawing problem
