Need help with these things

[The Undaddy]

First things first:

What I know:
-This is a network of points, some connected, kind of like a road system
-There are algorithms about them (find shortest path to,etc.)
-I need to use this

What I don't know:
-What it's called
-Aforementioned algorithms
-How to use this

Well, any assistance is welcomed, be it links to other sites or resources, or lengthy, difficult to understand explanations (I reckon there will be many).

 

[SineCosine]

I have no idea what these algorithms are.
But you could store these 'dots' in arrays.

(If they're units, great! if not, it's okay)
I'll assume you use co-ordinates.
This method will limit you to 8190 dots and will get slower as you add more dots.

I think you'll only notice the difference once you hit a large number.
The following was free-handed and might have some logical flaws.
I can't check because my WE has some error with it xD

globals
    private constant integer Array_Size = 1000 //Put it to some number you know you'll never reach in a game.
endglobals
//Well, store your stuff in an array.
struct Stuff

    real array X[Array_Size]
    real array Y[Array_Size]

    integer array NearestDot[Array_Size]
    integer Stored = 0

    method StoringStuff takes real x, real y returns nothing
        //Let's say you wanna' store a co-ordinate to your array.
        set X[Stored] = x
        set Y[Stored] = y

        set Stored = Stored + 1

    endmethod

    method RemovingCoordinate takes integer index returns nothing
        local integer i = index

        loop
        exitwhen i == Stored
            set X<i> = X[i+1]
            set Y<i> = Y[i+1]
        set i = i + 1
        endloop

        set X<i> = 0.0
        set Y<i> = 0.0
        set Stored = Stored - 1
    endmethod

    method FindingShortestPath takes nothing returns nothing
        //The following will work even if your &#039;dots&#039; are always moving, as long as you update your co-ordinates.
        //Inefficient for periodic path-finding, trust me.
        //If you want efficient, then your &#039;dots&#039; must never move.
        local integer FirstLoop = 0
        local integer SecondLoop = 0
        local real Check = 99999999.0 //Setting this to some crazy high number    
        local integer Selected = 0 //In case there is only one dot in your array
        local real Dist
        local real dx
        local real dy

        loop
        exitwhen FirstLoop == Stored

            loop
            exitwhen SecondLoop == Stored

                if FirstLoop != SecondLoop then //Well, we don&#039;t want the dot to compare with itself, do we?
                    set dx = X[FirstLoop] - X[SecondLoop]
                    set dy = Y[FirstLoop] - Y[SecondLoop]
                    set Dist = SquareRoot( dx * dx + dy * dy)

                    if Dist &lt; Check then
                        set Check = Dist
                        set Selected = SecondLoop
                    endif
                endif 

            set SecondLoop = SecondLoop + 1
            endloop
 
            set NearestDot[FirstLoop] = Selected
 
        set FirstLoop = FirstLoop + 1
        endloop
 
    endmethod
endstruct

</i></i></i></i>

 

[the Immortal]

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

The simplest, most suitable and fast algorithm you should use. It's written in the wiki, but basically you keep a list of all 'open' (for evaluation) nodes, what node you reached them from, and the cost to reach them. First the list contains only source and all distances are infinity (except source = 0).

Then you loop, doing:
Remove the node from the list with smallest dist.
Add all nodes reachable from it, and set that point as their 'from' point. (the point you reached them from). Set their dist to "from" point + distance between those two.
If a point is already in the list, update the info for it, but ONLY if new dist < previous dist.
Loop until current node with smallest dist is the destination node.

Not sure if I explained it well. There's a pseudocode that probably does it better (optimizations ftl..) in the wiki page.

Hope it helps.


EDIT: If they are scattered on a plane (i.e. you know their co-ordinates), check out the A Star algorithm. It does essentially the same, but uses a heuristic to further optimize the search.

 

[The Undaddy]

Well you got the basic idea, but I should have elaborated a bit more.

Yes they are coordinates and never move.Also only some of them are connected (ooh, emphasis), this means that we can't go from point 1 directly to point 6, we must pass trough point 2 (refer to picture in post #1).

Edit: Now checking the links you posted, immortal
You must spread some reputation before giving it to SineCosine again. :[

Edit2: Ok, I think i got it, the A-star thing is quite a nuisance,though.

 

[SineCosine]

I'm going out now, but if your question has not been answered by the time I get home (read: 4-5hours time) then I'll help you as best I can.

Okay, so here's what I know:
01) These points never, ever, ever move for the duration of the game.
02) Some are connected.
03) You want to know the shortest path from A to C but must pass through any number of Point Bs.

Here's what I want to know.
These.. Connections.. Must they be followed strictly?
Like, you must pass through these point Bs and never deviate from them.

So..
We have to include the possibility that some of these 'dots' will have 3 or more 'paths' to other dots.

Hmm..
I'll be going out now.

 

[The Undaddy]

Well, my question has been answered, as far as theimmortal giving me enough information for me to expand on goes, but I'll address your questions.

No,the points do not move.

These 'connections' mean you can go from point A directly to point B if they are connected.No connection means that you cant go from point A to point C.And if B and C are connected, we can go from B to C. (and vice versa, but let's keep it simple for this example)

So if we would like to go from A to C, we have to pass trough B, since no direct connection is available.

Therefore, yes, multiple paths are possible, otherwise this wouldn't be so hard

And since there are multiple paths, one should stand out.And which better to stand out than the shortest one.Hence trying to find it.

 

[SineCosine]

So..
My help is not required? o.0