• Register

The near future: Trains are no longer controlled by humans. Instead, artificial intelligence is used to handle traffic. Program the best AI, beat challenges on various maps and watch it fight other AIs in live, online matches!

Forum Thread
  Posts  
Getting started with pathfinding (Games : TrAInsported : Forum : Pathfinding : Getting started with pathfinding) Post Reply
Thread Options
Apr 10 2013 Anchor

You've gone through the tutorials and completed the challenges, but have no idea how to continue? Other players on the server seem to be doing much better than you and you'd like to join the ranks?
You've come to the right place!

Pathfinding is not an easy task. There are many approaches, each with their advantages and disadvantages.
TrAInsported could be a good platform for learning and testing simple pathfinding algorithms. Start with small maps though, because larger maps will need more tricks. 10 by 10 tiles should be a good size.

For beginners in pathfinding:

  • One of the most famous approaches is something called A*-Algorithm (spoken A-Star). There's a nice tutorial on that can be found here.
  • Here's a great visual example of pathfinding: Qiao.github.io (thanks to mccoyn for the link!)

For advanced users:

  • Since the number of lines you can use in each function is limited in trAInsported, a good idea for larger maps might be to analyse the map in ai.init, split it into "paths" and then use the dijkstra algorithm in ai.chooseDirection().
  • A Youtube video explaining Dijkstra step by step. (Thanks SpaceNinjaDino for the link!) This does not show you any code, it just explains how the algorithm works. So you'll really need to code it yourself!

If you get stuck, have any problems, or tipps and tricks, feel free to post in this forum!

Edited by: Germanunkol

Apr 11 2013 Anchor

Here is a pretty decent video on Dijkstra's Algorithm: Youtube.com

Apr 16 2013 Anchor

Could you explain a little what you mean by splitting into paths?

I now use BFS which is like Dijkstra with unweighted edges and only junctions as vertices but it's still slow for large maps.

Anyway thanks for the game. I really enjoy it.

Apr 16 2013 Anchor

Hey, thanks for the feedback :D

Hm, I think what you did was exactly what I meant by splitting into paths - only use the junctions as vertecies. When you're looking for a path, find the junctions between which the destination tile lies and then "dijkstra" your way to those junctions.
But I must admit that I have not tested this myself - can you tell me a bit about your current results? Do you get "taking too long" errors? And on what map size?

Apr 16 2013 Anchor

I'm not going into much testing now because my code is a little bit messy and I have to rework it entirely. It's my first project in lua :D

However for map 18x18 executing my implementation of BFS took at most 2500 executions in whole round (not sure if that was the worst case possible). But since the surface of the map (and number of junctions) grows quadratically then I guess for 30x30 it can take much more than 5000.
Though I don't see this as a downside. At least it's challenging.

The main reason I have to rewrite my code is I wasn't careful enough while reading docs and I didn't notice the ai.init provide whole description of the map. So my script is full of code doing something like map learning or deterministic exploring :D But I must say this version of the game would be interesting too :D

EDIT:
Without giving that array containing map layout it would be really hard to calculate edge length from time (since trains can block each other). But if the train object would contain for instance number of tiles which it ride through since the beginning of simulation it would be possible to discover map precisely.

Edited by: loblpavel

Apr 16 2013 Anchor

loblpavel wrote: The main reason I have to rewrite my code is I wasn't careful enough while reading docs and I didn't notice the ai.init provide whole description of the map. So my script is full of code doing something like map learning or deterministic exploring :D But I must say this version of the game would be interesting too :D

That's a great idea! Someone else also mentioned something similar, a game mode with a "fog of war" kind of gameplay. I might implement this at some point, if I find the time...

I will give this some more thought...

May 31 2013 Anchor

Hey man,
first of all: THANKS FOR THIS GAME!!!

I implemented a pathfinding algorithm using the junctions only, but still i'm getting "taking too long" errors quite to fast.

It even happens on 12x4 if i'm unlucky. And at this point i would have a few feature requests:
- a call (with only 500 lines), when a function takes too long ai.takenTooLong(methodName, train)
if the method has no train, train is nil/false
if ai.takenTooLong() takes too long ( :D ) it won't be called again!!! as this could be used for getting unlimited lines

- a game mode with all calls having 50000 lines
or maybe a specified number of recursive calls allowed (wich themselfes have a specific number of lines not counting to the actual call)

- and last but rly not least:
if it is anyhow possible: ADD A DEBUGGER!!!!
trust me man people would kiss your ass!!

Will also post these feature requests in the specific thread.

Reply to thread
click to sign in and post

Only registered members can share their thoughts. So come on! Join the community today (totally free - or sign in with your social account on the right) and join in the conversation.