   Ship movement on map - Checkpoints?
  HiIm doing a game similar to "sid meiers Pirates!" A lot of computer ships must go between different ports on the main map and im a bit confused on how to do it.My map is 1300x650 tiles and reaches from cyprus to japan, in modern times. To do a* pathfind on the fly with each ship spawning is to slow and to regid.My idea is to have checkpoints of some sort. Lets say a ship sets out from cyprus and is heading for india. It must navigate through zuez-channel etc. I also want ships to differ slighty when going from startPos to endPos, which they will not if i use a* pathfind (then they will always take the optimal route).Could i somehow set generic checkpoints on the map and ships find an acceptable route (each checkpoint could have data on how "vide" they are so open-sea checkpoints can be more then just a specific point, more like an checkarea)?Or do i need to set up "chains" of checkpoints, like routes and then hardcode each connection from one port to each other port?The problem is, if i have 50 or 100 ports, and each port needs to be told specifically how to send ships to EACH OTHER port, i end up with at least 2500 routes...   
Quote:Original post by sulimanMy map is 1300x650 tiles and reaches from cyprus to japan, in modern times. To do a* pathfind on the fly with each ship spawning is to slow and to regid.You may want to use some form of hierarchical pathfinding.Quote:My idea is to have checkpoints of some sort. Lets say a ship sets out from cyprus and is heading for india. It must navigate through zuez-channel etc. I also want ships to differ slighty when going from startPos to endPos, which they will not if i use a* pathfind (then they will always take the optimal route).Such 'checkpoints' are usually called nodes, what you're after is creating a nodegraph. As for variation in routes, in real life there are busy trade routes here and there because, well, those routes are pretty optimal. Either way, if you do want ships to take less optimal routes, then modify your A* implementation to take care of that. As for the actual sailing, ships don't need to move in a linear fashion between nodes. You could, for example, add some avoidance behavior, so they sail around other boats instead of crashing into them.Quote:Could i somehow set generic checkpoints on the map and ships find an acceptable route (each checkpoint could have data on how "vide" they are so open-sea checkpoints can be more then just a specific point, more like an checkarea)?Mixing 'areas' with nodes sounds like it'll make things more complicated. You probably don't need nodes in open sea, anyway, just nodes for ports and around land masses. A connection between two ports can be made if there's open sea in-between, without the need for additional nodes in that sea area.Quote:Or do i need to set up "chains" of checkpoints, like routes and then hardcode each connection from one port to each other port?The problem is, if i have 50 or 100 ports, and each port needs to be told specifically how to send ships to EACH OTHER port, i end up with at least 2500 routes...Manually linking nodes could easily cost too much work. You may want to write a tool that generates a nodegraph, based on a map that contains passable/impassable areas and a set of nodes.   ;  yes but how do i set up a nodegraph?What comes to mind is to manually setup a number of chain of nodes, to help ships get around some barriers like channels etc. A port can then more easily find a path of nodes to reach another port with its ships. It looks for nearby nodes, then link with a known "difficult passage chain" then links with the destination port nodes. Would this work?What i would like is to put down general nodes, and that ships kinda understands what nodes it should pick to get closer to its destination. Is this doable?   ;Quote:Original post by sulimanyes but how do i set up a nodegraph?The basics are simple: you have nodes and connections. You'll want to write a Node class that contains a list of references/pointers to other nodes. Then, you'd create an instance for every node in your graph, and link these nodes together. Such information can be hard-coded, but it's more flexible to store it in an external file. Since it sounds like you'll need a lot of nodes, I think it's worthwhile to create a quick tool to help you set up a nodegraph. Perhaps there are tools for this already, you may want to search around a bit.Quote:What comes to mind is to manually setup a number of chain of nodes, to help ships get around some barriers like channels etc. A port can then more easily find a path of nodes to reach another port with its ships. It looks for nearby nodes, then link with a known "difficult passage chain" then links with the destination port nodes. Would this work?Go ahead and try it out. I suggest determining the node connections beforehand though. Additional nodes are only required when a direct connection wouldn't make sense, for example when there's land between two ports.Quote:What i would like is to put down general nodes, and that ships kinda understands what nodes it should pick to get closer to its destination. Is this doable?That's exactly what a nodegraph is for. You'd run pathfinding over the graph to determine the (shortest) path from node A to B.EDIT: Rather than just storing references or pointers to other nodes, you'll also want to store the cost (length or travel time) of this connection, to make pathfinding easier. Pseudocode:class Connection:   Node* node1   Node* node2   float costclass Node:   Point position   Connection* connections[]   addConnection(other_node): newConnection = Connection(this, other_node) connections.add(newConnection) other_node->connections.add(newConnection) [Edited by - Captain P on June 4, 2009 3:01:31 PM];  Then im a bit confused. The a* i use (of which most is borrowed but I understand some of it) works with a grid-pattern (a normal tile-world). How can i do pathfind over a set of nodes that are not positioned at all like a grid?By the way, thanks for all your help here:)   ;Quote:Original post by sulimanThen im a bit confused. The a* i use (of which most is borrowed but I understand some of it) works with a grid-pattern (a normal tile-world). How can i do pathfind over a set of nodes that are not positioned at all like a grid?The catch is that the grid is a kind of nodegraph, albeit a disguised one. Or actually, it can be interpreted as a nodegraph. Every tile is a node, and connections with the 8 (or 4, if you don't want diagonal movement) neighboring nodes are automatically assumed. Impassable tiles are discarded.With a nodegraph such as I described, you're working with explicit nodes and connections. Instead of looking at the neighboring tiles, you'd check what connections a node has. That tells you what nodes it's neighboring. The same principles apply, it's just that the data comes in a different form.Quote:By the way, thanks for all your help here:)No problem. :)   