Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.
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!
0 · ·