Random map explore! any better algo?

[mysnow]

now ,I use player postion as coordinate origin point at init time, each squares length is 2*R,slipt map, use backtracking,try to found next destination in 8 direction and record the history postion ,if fond there have not load scene,refresh map...,it can success to explore the whole map and found the next level portal
the problem is inefficiently use this method,some one know a btter method,when refresh map!

[Nesox]

http://www.lalena.com/AI/Tsp/

[farfle]

I assume you're doing some graph simplifications on top of the navcells, otherwise a TSP tour would be pretty crap in most of the D3 worlds. Any hints? I'm currently just performing edge contractions based on distance between navcell centres but this can result in some pretty suboptimal summary nodes, especially in places like the A3 keep depths with lots of small rooms and doorways.

Also, isn't a TSP tour sometimes a little strange when you want to explore the whole world graph and end up far from the tour start location? Can your TSP implementation produce hamiltonian paths or something?

[farfle]

Durr..... I wish I'd thought about this for more than a second before making that post. Tried it today with a simple 2-opt local search TSP solution and adding a single dummy node. Tada, hamiltonian path :/