The forum is read-only. New threads, replies and edits are disabled.
low cost pathfinding without stairs
krumza August 16th, 2018

subj.

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?

Gio August 20th, 2018

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.

flowChartEditor.js