CRPL code for runner-like movement

[eduran]

I am working on a unit that is supposed to randomly move around digitalis, exactly like runners do. Is there any chance to get access to the runner script? Is their movement even coded in CRPL?

[Annonymus]

I think their movement is not coded in CRPL but you should be able to script it like any normal unit that moves randomly over terrain while checking for getdigitalis = true.

[Clean0nion]

I think their movement is not coded in CRPL but you should be able to script it like any normal unit that moves randomly over terrain while checking for getdigitalis = true.

Copy the Glider code from Chanson and change GetTerrain for GetDigitalis. I'll code it up for you in a bit if you're patient.
(one thing I can't do is make sprites or make the image rotate when it moves)

[eduran]

I should have been more specific: completely random movement is not the problem, but doing that will make the unit mostly wriggle around its starting point. Runners seem to have some sense of direction. Sure, every now and again they will turn on the spot, but most of the time their movement seems pretty fluid (for lack of a better word).
Check the code from Chanson an a rail that is 3+ cells wide and compare that to how runners behave on a wide stretch of Digitalis. You'll see what I mean.

Edit: added a modified version of Chanson for demonstration purposes.

[knucracker]

Runners do something that is kinda tough to do in CRPL and is fairly CPU intensive.  It can be done, you just have to be smart about it.
Runners first do a 'flood fill' algorithm out from their starting location.  This floodfill spreads across all connected digitalis and returns an array of reachable cells (cells that are connected to the Runner one way or another).  This floodfill is limited so that it won't crawl more than 2500 cells total though (a performance enhancement).

Once an array of possible locations are found, one is chosen at random.  Once chosen, and A* path-finding search is performed to determine the path of movement that the Runner should take.  If at any point in it journey the Runner gets stuck, it just starts over and picks another location.

The produces runners that will explore 'rooms' made from digitalis that are only connected by narrow 'hallways'.  But this kind of movement algorithm can be CPU intensive and also difficult to code up.  A simpler movement algorithm might be to just move straight till movement is no longer possible.  Then do something like turn a random direction, or rotate left/right till movement is possible again.  Even movement that always attempts to move towards some randomly chosen player units might be interesting.

[eduran]

Thanks for the explanation. I actually went ahead and implemented a crude A* algorithm in CRPL. It works on (very) small maps, but runs into the '1 million operations per frame' limit rather fast. I guess I'll try to optimize it and see if I can stretch the pathfinding over several frames.

Edit: Success! I've attached a demo map to showcase what my CRPL-A* implementation can do. Left click anywhere onto the digitalis growth to create a destination (marked by a totem). The core will try to find the shortest path towards it and start moving if it finds one. You can add a new destination once the core reaches its goal. The cells covered in creeper have all been considered by the algorithm. Performance is still an issue, so I am not sure if this will ever be used in a real map. It could work if the area covered is small enough.

[Lord_Farin]

Thanks for the explanation. I actually went ahead and implemented a crude A* algorithm in CRPL. It works on (very) small maps, but runs into the '1 million operations per frame' limit rather fast. I guess I'll try to optimize it and see if I can stretch the pathfinding over several frames.

Edit: Success! I've attached a demo map to showcase what my CRPL-A* implementation can do. Left click anywhere onto the digitalis growth to create a destination (marked by a totem). The core will try to find the shortest path towards it and start moving if it finds one. You can add a new destination once the core reaches its goal. The cells covered in creeper have all been considered by the algorithm. Performance is still an issue, so I am not sure if this will ever be used in a real map. It could work if the area covered is small enough.

Ok, here's my 2c on the algorithm. I'm very bad at CRPL at this point, so I'll leave the coding to others.
Destination selection:
- Determine by a flood algorithm which digitalis growth areas could possibly be connected (once per map).
- Given a runner, pick a random digitalis growth cell in the accessible growth area. Order it to move there.
Path finding options:
- A* or some similar algorithm on growth area.
- If next move is impossible, wait for some time before picking new location. During those, check, and continue if possible.
- Pick new location if movement remains impossible.

This will create units that are likely to stick close to areas of digitalis advancement. This can be a fun interaction with the player units. As a downside, in the presence of digitalis "shortcuts"/"wormholes", the runners won't attempt to take a diversion if the shortcut is not available.

[knucracker]

Thanks for the explanation. I actually went ahead and implemented a crude A* algorithm in CRPL. It works on (very) small maps, but runs into the '1 million operations per frame' limit rather fast. I guess I'll try to optimize it and see if I can stretch the pathfinding over several frames.

Edit: Success! I've attached a demo map to showcase what my CRPL-A* implementation can do. Left click anywhere onto the digitalis growth to create a destination (marked by a totem). The core will try to find the shortest path towards it and start moving if it finds one. You can add a new destination once the core reaches its goal. The cells covered in creeper have all been considered by the algorithm. Performance is still an issue, so I am not sure if this will ever be used in a real map. It could work if the area covered is small enough.

Wow... that's a serious piece or work.  Very impressive.  I didn't expect anybody to actually sit down and pull that off in CRPL :)  It isn't the easiest of algorithms to visualize and you have to juggle several data structures to get it to work.

[Kingo]

Thanks for the explanation. I actually went ahead and implemented a crude A* algorithm in CRPL. It works on (very) small maps, but runs into the '1 million operations per frame' limit rather fast. I guess I'll try to optimize it and see if I can stretch the pathfinding over several frames.

Edit: Success! I've attached a demo map to showcase what my CRPL-A* implementation can do. Left click anywhere onto the digitalis growth to create a destination (marked by a totem). The core will try to find the shortest path towards it and start moving if it finds one. You can add a new destination once the core reaches its goal. The cells covered in creeper have all been considered by the algorithm. Performance is still an issue, so I am not sure if this will ever be used in a real map. It could work if the area covered is small enough.

Wow... that's a serious piece or work.  Very impressive.  I didn't expect anybody to actually sit down and pull that off in CRPL :)  It isn't the easiest of algorithms to visualize and you have to juggle several data structures to get it to work.

Just goes to show the amazing things you can do with code :)