A* in events system: Find lowest F value

Get help using Construct 2

» Wed Dec 12, 2012 1:06 am

Hey Peeps,
I'm working on a tile based tactical board game. I've implemented the A* path finding algorithm in the events system and it works fine, but its a tad slow. The boards typically range from 15x10 (1.5:1 ratio) so there not huge. One particular part of the algorithm I had to 'hack' together was choosing the lowest F value. I'm not using arrays instead I've got instance variables storing the G,H & F on each tile. This means I need to select the lowest F value which is stored in an instance variable. Currently I'm using: For each ordered (pf_F, ascending) then i stop the loop straight away as it has applied the required actions to the first instance (which has the lowest F value). So I'm wondering is there any possible optimization or more efficient way of selecting the lowest F without calling a for each ordered loop every iteration? I know system: pick instance by instance variable (=, !=, <, >, <=, =>) doesn't exist in C2 currently but it would be great. can anyone help?
B
8
S
3
G
2
Posts: 10
Reputation: 2,077

» Wed Dec 12, 2012 1:41 am

I think if you want better performances you should work with arrays not objects. Unless you're not using a grid based graph (?) otherwise array is probably the optimal datastructure.

But to answer your question, the "foreach ordered" on top of looping over all instance, probably runs a sorting algorithm before (which behind the scene probably compare each instance with each other at some point so you have like a hidden nested loop).
Maybe should just do a simple foreach like that:
[code]
+on whatever
local number lowest = 99999
local number lowestUID = -1

+ system: foreach object
+ object: variable < lowest
-> system: set lowest to object.variable
-> object: set lowestUID to object.UID

+ object: pick by UID lowesUID
-> do whatever[/code]Yann2012-12-12 01:44:26
B
68
S
22
G
14
Posts: 1,486
Reputation: 16,565

» Wed Dec 12, 2012 9:37 am

If there were multiple that match the low value, instead of picking by the UID you could then "compare variables" to pick all that matched that lowest value Yann's routine found.
(although that would be even slower, as it its basically a built in "For each" again to select all that match.)

B
243
S
63
G
33
Posts: 903
Reputation: 40,791