nanodeath / crowlib Goto Github PK

Hi, I noticed that there is an error when removing an edge or vertex in a connected graph (no x,y coordinates) .
Here are some functions that I use to delete my connected edges and vertices.

note that "graphForTraversal" in an instance of crow.Graph()

  function removeEdgeInGraphForTraversal(edge){
        var sourceVertex = graphForTraversal.getNode(
            edge.sourceVertex().getId()
        );
        var destinationVertex = graphForTraversal.getNode(
            edge.destinationVertex().getId()
        );
        removeVertexInConnections(destinationVertex, sourceVertex.connections);
        removeVertexInConnections(sourceVertex, destinationVertex.connections);         
    }

   function removeVertexInGraphForTraversal(vertex){
        graphForTraversal.removeNode(
            graphForTraversal.getNode(vertex.getId())
        );
        var node = findVertexInGraphForTraversalNodesAfterItWasDeleted(
            vertex
        );
        $.each(node.connections, function(){
            var connection = this;
            var connectedNode = graphForTraversal.getNode(connection.id);
            removeVertexInConnections(vertex, connectedNode.connections);
        });          
    }

    function removeVertexInConnections(vertex, connections){
        for(var j in connections){
            var connection = connections[j];
            if(connection.id == vertex.getId()){
                connections.splice(j,1);
            }
        }
    }

    function findVertexInGraphForTraversalNodesAfterItWasDeleted(vertex){
        for(var i in graphForTraversal.nodes){
            var node = graphForTraversal.nodes[i];
            if(node.id == vertex.getId()){
                return node;
            }
        }
    }

It would be nice to preprocess the code before it gets passed to the Google Closure compiler. I can think of two particular things that we could do with that:

• Strip out lines containing an assert to speed up performance.
• Transform JSDoc-style arrays to Google Closure-style arrays, i.e. String[] -> Array.. Don't know why they're different, but it's annoying.

Per user feedback, Crow needs better documentation for how to actually get a Crow file on the page.

Algorithm to implement

Is it really necessary to have that tweak in the Array.prototype property?
It has the mean consequence that every for...in loop in the code of anybody using this library will fail if not checking for hasOwnProperty in EVERY loop body, making the code look way uglier in big projects.

Moreover, i thought extending native types prototypes was generally bad practice, probably for this reason.

Use RaphaelJS. It's cool.

This library might see more interest and adoption if I rip out all the Google Closure bits, which might have made sense 9 years ago, but hasn't for a long time.

New version should ideally use TypeScript, but I might use Kotlin/JS just cuz, if the efficiency would be comparable.

Hi maybe Im missing something but I did a rake command in the crow folder and I had a crow.mini.js generated in dist. I added the script file in my html. I see GridNode BaseNode and Node when I type crow in my javascript console but I dont see ConnectedNode. How is that ? am I missing something?

Thanks !

perfTests is broken again in 0.4.0. Need to investigate why -- I think it's the test, not the code, though.

would this be a good choice for pathfinding on a hex grid?

WIth fixed distances, BFS can be used to calculate a shortest path. It's faster than Dijkstra's, too.

Right now, the way algorithms are chosen is pretty dumb. By default, getNodes uses a linear search algorithm unless you choose BFS explicitly, and findGoal will use Dijkstra's unless you choose A* explicitly. The goal behind writing a pathfinding library such as Crow is to provide a powerful but simple API. In other words, the choosing of an algorithm should be a declarative process, not an imperative one.

Ideally, we'd be looking at something like this (written in plain English):

I want to find the shortest path between point A and point B. It doesn't have to be exact; a reasonable guess is okay. The target isn't expected to move. I want the complete path. Once the path is generated, I'm done -- I don't care if the graph it was built upon changes.
-> This would return A*, limit undefined, and be baked (unchangeable; unassociated with graph).

I want to find the shortest path between point A and an unknown node matching condition f(x). It can be a guess. Target doesn't move. Complete path required. Done afterwards.
-> This would return Dijkstra's, limit undefined, and be baked.

I want to know if point B is reachable from point A.
-> This would either be BFS or A*.

When picking attributes for the algorithm, there should be a number of descriptors available. Some ideas are: MUST_NOT, SHOULD_NOT, MAY, SHOULD, MUST. This way, you can say I want heuristics, but don't have to have them (SHOULD); or I don't really care (MAY), or it has to support moving target optimizations (MUST), etc.

On version CrowLib-0.6.1.tgz

Crow was designed principally for games, which would presumably take place on a grid (i.e. 2-dimensional Cartesian graph with integer coordinates). Some have expressed an interest in a more arbitrary system, one that didn't rely on any particular graph format; such a thing would allow something like cities to be represented, with a provided distance. Neighbors would also be provided, instead of determining neighbors by proximity on a grid.

This is already possible with Crow -- one can simply override the getNeighbors method to provide neighbors, and the rest should just work. However, this could be simplified (and documented more) for client developers. There are several actions to take:

1. Modify BaseNode or create a new Node class that does not require x-/y-coordinates. The node should also have an arbitrary id (which is used as a key in the graph), instead of one dependent on those coordinates
2. Modify the Graph's findGoal method, if possible, to be static -- you don't strictly need an instance of a graph to find the path between two nodes.
3. Add documentation describing these new changes.

Ruby 1.8.7 seems to work fine, though.

max@max-Vostro-1400:~/Dropbox/Javascript/CrowLib$ rake
Checking dependencies...
/home/max/Dropbox/Javascript/CrowLib/build/google_closure/library/closure/bin/calcdeps.py --input=src/crow/All.js --path=/home/max/Dropbox/Javascript/CrowLib/build/google_closure/library --path=src
rake aborted!
No such file or directory - /home/max/Dropbox/Javascript/CrowLib/build/google_closure/library/closure/bin/calcdeps.py --input=src/crow/All.js --path=/home/max/Dropbox/Javascript/CrowLib/build/google_closure/library --path=src

Tasks: TOP => default => build_crow => prepare_build
(See full trace by running task with --trace)

See https://developers.google.com/closure/library/docs/calcdeps

I'm trying to use the same code for both a standalone client and a server controlled client.

It would be nice to to use node.js style requires and then browserify(https://github.com/substack/node-browserify) for packaging to work better in the node.js world.