low cost pathfinding without stairs


HI, Gio and all.

as a matter of fact, the title says it all. I do the editor of block diagrams.

And already completed it, except that I don't like the way connecting my blocks.

I've tried several libraries. but the desired result is not obtained (it should be noted that I didn't even do A-* mechanism of the library, Wade).

Step by step what I do - split the screen into cells, translate the coordinates of objects in the grid coordinates, then build an array and look for the path in it, then draw lines and points. I do not like the results - either the steps or the algorithm chooses the path - down-right, although visually it would be more correct - right-down. Ie, to me it is necessary that the devices were connected as fewer kinks and lines and it does not give complications in distances between the blocks.

Something similar you have in the flow-chart editor, but I have a completely different specificity of blocks - the number of inputs is limited, each has its own property, and I do not implement through ctx primitives, but through sprites,

 I would love to make a strict rule for a connecting object-1 point and two lines, but alas, the user wants to move the blocks and the block with the line should not intersect.

as a connector between the blocks I use

let joint = {
lines:[],//array of sceneobjects
dots:[],//array of sceneobjects
begin:{},//grid coordinates of begin
begin_sprite:{],//link to sprite of begin 
end:{},//grid coordinates of end
end_sprite:{}//link to sprite of end

I duplicate the coordinates because when a line is drawn it has no reference to another block so the connector can be bound either just to a point or to a specific sprite.

in General, Gio (or someone else) do you know a algorithm that would be good to connect blocks at any distance with the least number of angles and the least expensive pathfinding algorithm?

1 Comment

Hi krumza

I'm not sure that you need a full-blown pathfinding algorithm for that. I think you can do what we did with our flow chart editor. I understand it's a bit different, but it's also somewhat similar. Also if I remember correctly, we don't draw canvas primitivies (i.e. lines) for our flow chart editor, but we use a small rectangular sprite for each line.

It's not a perfect solution, if you have very complicated graphs you can have some intersections sometimes. I think this may be unavoidable, regardless of the algorithm. But what we have is fast.

Basically we came up with our own heuristic algorithm that tries a few different possible combinations. It then gives a score to each of these possible combinations - so for example, if there is an intersection, it adds +1000 to the score; if there is an angle, it adds +100, etc. Then it chooses the graph with the lowest score.

I am happy to share our code for it. I helped design the algorithm, but didn't write the code myself, so don't blame me for the code style :)

It's attached, hopefully you can make sense of it. Specifically, scroll down to line ~1400 and have a look at our implementation of the Line class. In the comments, there are also links to the algorithms that we have used to determine if a line intersects an AABB, intersects itself, etc.

Post a reply
Add Attachment
Submit Reply
Login to Reply