I think that I have found a workable way of doing this, copying as much as I can from the A* system but removing the heuristic element. I am not set up to produce .patch files, but something along the same lines should work for Standard, too. The following changes are needed in simconvoi.cc:

`@@ -5670,33 +5670,33 @@ public:`

{

return master->get_waytype();

};

virtual bool ist_befahrbar( const grund_t* gr ) const

{

return master->ist_befahrbar(gr);

};

virtual bool ist_ziel( const grund_t* gr, const grund_t* )

{

return gr->get_depot() && gr->get_depot()->get_besitzer() == master->get_besitzer() && gr->get_depot()->get_tile()->get_besch()->get_enabled() & traction_type;

};

virtual ribi_t::ribi get_ribi( const grund_t* gr) const

{

return master->get_ribi(gr);

};

- virtual int get_kosten( const grund_t*, const sint32, koord from_pos)

+ virtual int get_kosten( const grund_t* gr, const sint32, koord from_pos)

{

- return 1;

+ return master->get_kosten(gr, 0, from_pos);

};

};

And in route.cc:

`@@ -191,168 +191,204 @@ uint8 route_t::GET_NODES(ANode **nodes)`

dbg->fatal("GET_NODE","called while list in use");

return 0;

}

void route_t::RELEASE_NODES(uint8 nodes_index)

{

if (!_nodes_in_use[nodes_index])

dbg->fatal("RELEASE_NODE","called while list free");

_nodes_in_use[nodes_index] = false;

}

/* find the route to an unknown location

* @author prissi

*/

-bool route_t::find_route(karte_t *welt, const koord3d start, fahrer_t *fahr, const uint32 /*max_khm*/, uint8 start_dir, uint32 weight, uint32 max_depth)

+bool route_t::find_route(karte_t *welt, const koord3d start, fahrer_t *fahr, const uint32 max_khm, uint8 start_dir, uint32 weight, uint32 max_depth)

{

bool ok = false;

// check for existing koordinates

const grund_t* g = welt->lookup(start);

- if (g == NULL) {

+ if (g == NULL)

+ {

return false;

}

const uint8 enforce_weight_limits = welt->get_settings().get_enforce_weight_limits();

// some thing for the search

const waytype_t wegtyp = fahr->get_waytype();

// memory in static list ...

if(!MAX_STEP)

{

INIT_NODES(welt->get_settings().get_max_route_steps(), welt->get_groesse_x(), welt->get_groesse_y());

}

INT_CHECK("route 227");

- // arrays for A*/Dijkstra's Algorithm

- //static

- vector_tpl<ANode*> open;

- vector_tpl<ANode*> close;

+ // nothing in lists

+ // NOTE: This will have to be reworked substantially if this algorithm

+ // is to be multi-threaded anywhere: a specific vector or hashtable will

+ // have to be used instead.

+ welt->unmarkiere_alle();

+

+ // there are several variant for maintaining the open list

+ // however, only binary heap and HOT queue with binary heap are worth considering

+#if defined(tpl_HOT_queue_tpl_h)

+ // static

+ HOT_queue_tpl <ANode *> queue;

+#elif defined(tpl_binary_heap_tpl_h)

+ //static

+ binary_heap_tpl <ANode *> queue;

+#elif defined(tpl_sorted_heap_tpl_h)

+ //static

+ sorted_heap_tpl <ANode *> queue;

+#else

+ //static

+ prioqueue_tpl <ANode *> queue;

+#endif

// nothing in lists

- open.clear();

+ queue.clear();

// we clear it here probably twice: does not hurt ...

route.clear();

// first tile is not valid?!?

- if( !fahr->ist_befahrbar(g) ) {

+ if(!fahr->ist_befahrbar(g))

+ {

return false;

}

ANode *nodes;

uint8 ni = GET_NODES(&nodes);

uint32 step = 0;

ANode* tmp = &nodes[step++];

if (route_t::max_used_steps < step)

+ {

route_t::max_used_steps = step;

+ }

tmp->parent = NULL;

tmp->gr = g;

tmp->count = 0;

+ tmp->g = 0;

// start in open

- open.append(tmp);

+ queue.insert(tmp);

//DBG_MESSAGE("route_t::find_route()","calc route from %d,%d,%d",start.x, start.y, start.z);

const grund_t* gr;

- do {

+ do

+ {

// Hajo: this is too expensive to be called each step

- if((step & 127) == 0) {

+ if((step & 127) == 0)

+ {

INT_CHECK("route 264");

}

- tmp = open[0];

- open.remove_at( 0 );

+ ANode *test_tmp = queue.pop();

- close.append(tmp);

+ // already in open or closed (i.e. all processed nodes) list?

+ if(welt->ist_markiert(test_tmp->gr))

+ {

+ // we were already here on a faster route, thus ignore this branch

+ // (trading speed against memory consumption)

+ continue;

+ }

+

+ tmp = test_tmp;

gr = tmp->gr;

+ welt->markiere(gr);

-//DBG_DEBUG("add to close","(%i,%i,%i) f=%i",gr->get_pos().x,gr->get_pos().y,gr->get_pos().z,tmp->f);

// already there

- if( fahr->ist_ziel( gr, tmp->parent==NULL ? NULL : tmp->parent->gr ) ) {

+ if(fahr->ist_ziel(gr, tmp->parent == NULL ? NULL : tmp->parent->gr))

+ {

// we added a target to the closed list: check for length

break;

}

// testing all four possible directions

- const ribi_t::ribi ribi = fahr->get_ribi(gr);

- for( int r=0; r<4; r++ ) {

+ const ribi_t::ribi ribi = fahr->get_ribi(gr);

+ for(int r = 0; r < 4; r++)

+ {

// a way goes here, and it is not marked (i.e. in the closed list)

grund_t* to;

- if( (ribi & ribi_t::nsow[r] & start_dir)!=0 // allowed dir (we can restrict the first step by start_dir)

- && koord_distance(start.get_2d(),gr->get_pos().get_2d()+koord::nsow[r])<max_depth // not too far away

+ if((ribi & ribi_t::nsow[r] & start_dir) != 0 // allowed dir (we can restrict the first step by start_dir)

+ && koord_distance(start.get_2d(),gr->get_pos().get_2d()+koord::nsow[r]) < max_depth // not too far away

&& gr->get_neighbour(to, wegtyp, ribi_t::nsow[r]) // is connected

&& fahr->ist_befahrbar(to) // can be driven on

- ) {

- // already in open list?

- if (is_in_list(open, to)) continue;

- // already in closed list (i.e. all processed nodes)

- if (is_in_list(close, to)) continue;

+ && !welt->ist_markiert(to) // Not in the closed list

+ )

+ {

weg_t* w = to->get_weg(fahr->get_waytype());

if (enforce_weight_limits && w != NULL)

{

// Bernd Gabriel, Mar 10, 2010: way limit info

const uint32 way_max_weight = w->get_max_weight();

max_weight = min(max_weight, way_max_weight);

if(enforce_weight_limits == 2 && weight > way_max_weight)

{

// Avoid routing over ways for which the convoy is overweight.

continue;

}

}

// not in there or taken out => add new

ANode* k = &nodes[step++];

if (route_t::max_used_steps < step)

+ {

route_t::max_used_steps = step;

+ }

k->parent = tmp;

k->gr = to;

- k->count = tmp->count+1;

+ k->count = tmp->count + 1;

+ k->g = tmp->g + fahr->get_kosten(to, max_khm, gr->get_pos().get_2d());

-//DBG_DEBUG("insert to open","%i,%i,%i",to->get_pos().x,to->get_pos().y,to->get_pos().z);

// insert here

- open.append(k);

+ queue.insert(k);

}

}

// ok, now no more restrains

start_dir = ribi_t::alle;

- } while( !open.empty() && step < MAX_STEP && open.get_count() < max_depth );

+ } while(!queue.empty() && step < MAX_STEP && queue.get_count() < max_depth);

INT_CHECK("route 330");

//DBG_DEBUG("reached","");

// target reached?

- if(!fahr->ist_ziel(gr,tmp->parent==NULL?NULL:tmp->parent->gr) || step >= MAX_STEP) {

- if( step >= MAX_STEP ) {

+ if(!fahr->ist_ziel(gr, tmp->parent == NULL ? NULL : tmp->parent->gr) || step >= MAX_STEP)

+ {

+ if( step >= MAX_STEP )

+ {

dbg->warning("route_t::find_route()","Too many steps (%i>=max %i) in route (too long/complex)",step,MAX_STEP);

}

}

- else {

+ else

+ {

// reached => construct route

route.clear();

route.resize(tmp->count+16);

- while(tmp != NULL) {

+ while(tmp != NULL)

+ {

route.store_at( tmp->count, tmp->gr->get_pos() );

//DBG_DEBUG("add","%i,%i",tmp->pos.x,tmp->pos.y);

tmp = tmp->parent;

}

ok = !route.empty();

}

RELEASE_NODES(ni);

return ok;

}

I also recommend the following changes in route.h for consistency, although they are not essential:

`@@ -39,35 +39,37 @@ protected:`

private:

// Bernd Gabriel, Mar 10, 2010: weight limit info

uint32 max_weight;

public:

// this class save the nodes during route search

class ANode {

public:

ANode * parent;

const grund_t* gr;

uint32 f, g;

uint8 dir;

uint16 count;

inline bool operator <= (const ANode &k) const { return f==k.f ? g<=k.g : f<=k.f; }

- // next one only needed for sorted_heap_tpl

+#if defined(tpl_sorted_heap_tpl_h)

inline bool operator == (const ANode &k) const { return f==k.f && g==k.g; }

- // next two only needed for HOT-queues

- //inline bool is_matching(const ANode &l) const { return gr==l.gr; }

- //inline uint32 get_distance() const { return f; }

+#endif

+#if defined(tpl_HOT_queue_tpl_h)

+ inline bool is_matching(const ANode &l) const { return gr==l.gr; }

+ inline uint32 get_distance() const { return f; }

+#endif

};

private:

static const uint8 MAX_NODES_ARRAY = 2;

static ANode *_nodes[MAX_NODES_ARRAY];

static bool _nodes_in_use[MAX_NODES_ARRAY]; // semaphores, since we only have few nodes arrays in memory

This should suffice for it to work in Standard, I think. Do let me know if there are any queries or if you think that anything should be done differently.

**Edit**: My implementation of Dijkstra's algorithm above contained an error (failing to add the cost of the last node), which I have now corrected.

**Edit 2:** Another error in the implementation: I had forgotten to initialise tmp->g. This is now corrected above.