How to find shortest path - special problem

I just don't know how to solve this, so I'm posting it right here.

The problem of 'how to find the shortest path between two points'

seems to be very complicated to me in the following special case:

In my game the world bases on a map with x and y coordinates. The

map size goes from -2147483648 to +2147483647 (that are

about 1.84 ^ 19 fields.) . It is possible to go into 8 directions from

every field to the next field (north, northeast,...). This map has

2 types of fields (or, 2 relevant for my problem): water and land.

Players now have ships in which they can move around. They can

enter the distance in fields and direction (in degrees) they want to

drive with the ship.

So, instead of players driving around with the ships, I want computer

units to be able to drive around this map, to any position they want.

Now, the problem is that this whole-game is based on text. That

means, that every field is like a room: It must be loaded before

a player can get in. (for those who know, its MUD.-like, actually

I'm doing this with LPmud driver in LPC).

Because loading of every room is too expensive, and I only know

wether there is water or not after I loaded the room, (the ships

actually don't load every room, the load every maxdistance/ 10 one

room and check this one room - so 'hops' are possible)

I made the following hack:

I made a bounding box around every continent and made a modified

crash&turn algorithm to find the way from the starting point to

the nearest point outside of the box. (This crash&turn method

already works for the whole way between A-B, but it loads tons of

rooms, thats why its too expensive).

Now i have to find the way from the one nearest point outside the

box to the other nearest point outside the box. I know now -

without loading any rooms, that there is no land outside these

boxes. (I save the lower left and upper right coordinate in an file,

I make those boxed manually).

I'm pretty happy that I've gotten so far without any help (hey, I'm

totally new to programming), but now I have no idea how to find

the way between those points around the boxes - without this

crash&turn method, which is too expensive.

Any ideas? I read a lot about graphs and A' and algorithms, but

they dont seem to fit my needs... (as far as I understand them..)

thx for any help!


Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!