Create AI for Battle Mode

Author: hikerstk From a discussion on IRC: (10:04:59) hiker: Termina1: we don't have any track information for 3SB (three strike battles)(10:06:01) hiker: Termina1: so it would involve either adjusting the exporter to get this information, or (even better) to automatically get this information from the tracks (10:06:12) hiker: E.g. the tracks could specify 'drive on textures t1, t2, t3, ...) (10:09:07) Auria: for 3 strikes AI, I'd say just start by making a graph variant that is not oriented (10:09:20) Auria: and make the AI aware of it so that it can drive in both directions of each graph segment (10:09:26) hiker: Auria: well, that won't work well for more open arenas (10:09:27) Auria: that would not be sufficient but would be a good start (10:10:39) hiker: Auria: We should have one approach to all arenas. (10:10:46) hiker: Otherwise there will always be border cases. (10:20:36) Auria: hiker: that's why I suggest one approach that is drivelines ;) (10:27:39) hiker: Auria: I admit I am not entirely sure how to handle the 3sb (10:27:53) hiker: The current driveline structure is too limited, since it only allows for quads (10:28:18) Auria: I don't see this as a problem? (10:29:29) hiker: Well, we can have at most 3 branches (unless the branching off quads overlap) (10:29:55) hiker: Hmm - maybe that could actually be relaxed. (10:30:05) hiker: I think that's just a case of what the track exporter exports atm, ... (10:30:19) hiker: i.e. it uses one line of the quad it is forking off or so. (10:30:28) hiker: So the actual implementation could probably use more (10:30:43) Auria: ah I thought they could overlap (10:30:43) KroArtem: need to go now, good night/morning and good luck ;) (10:30:51) Auria: gn KroArtem! (10:31:07) KroArtem left the room (quit: Quit: (xchat 2.4.5 )). (10:31:30) Auria: but that's an implementation detail, not a design-level issue ;) (10:32:20) hiker: Yes, but I was somehow thinking that the current graph structure is not flexible enough ... while in fact it might be (10:32:48) hiker: Ideally (imho) the arenas should specify which textures to use (instead of creating the drivelines) (10:32:55) hiker: Which means we have triangles anyway. (10:33:08) Auria: hmm could be done (10:33:10) hiker: Adding support for triangles to the graph structure would be reasonable easy (10:33:26) Auria: but the whole graph code needs to be special-cased for 3 strikes then :) (10:33:27) Auria: * :( (10:33:46) hiker: Not really. (10:34:15) hiker: The naming might be a bit bad (i.e. 'quads' might be used, while 'sector' would be better, and the quad graph would become a sector graph) (10:34:33) Auria: I guess we need to check if performance would be hurt, since the current implementation was not built to handle so many nodes (or was it?) (10:35:06) hiker: Yes, that might be a bit of a problem: (10:35:28) hiker: as long as the karts are on track, it will search close to the current sector to find the next one (10:35:38) hiker: But that is based on the numbers iirc (10:35:57) hiker: But that would be easy enough to improve: (10:36:18) hiker: For the AI code we probably need a better item detector anyway, e.g. to find any items close by without iterating over all of them (10:36:46) hiker: So the usual 'hashing' approach can be used: divide the track plane into nXm rectangles (10:36:56) hiker: And in each rectangle store which sectors are there. (10:37:17) hiker: Then you only have to check the sectors that are in the current 'hashed rectangle' (10:37:27) Auria: yeah ok. either that or a tree structure, performance-wise I think they'd be similar for our purposes (10:37:39) hiker: That could be a template, which we could also use for items (10:38:13) hiker: So I wouldn't worry about performance, if this part should become a problem, it's easy to fix. (10:38:35) Auria: agreed (10:38:37) hiker: The quads should use an abstract base class, so that the graph can handle quads and triangles (10:38:53) hiker: It only needs a 'is inside' operation, then everything else should sort itself out (10:39:22) hiker: Though with triangles the 'follow the center of sector' approach doesn't work as nicely anymore (10:39:43) hiker: since on straights (made out of triangles) the karts would drive left, right, left, right, ... (10:40:43) Auria: the AI will need to think much more ahead of time if we use triangles (10:40:57) Auria: a quad-by-quad approach will no longer work be there (10:41:04) hiker: nod (10:41:17) hiker: But it would need some kind of path finding anyway (10:41:27) Auria: I guess so (10:41:42) hiker: And the path finding would give the control points to use for steering I'd guess (10:41:42) Auria: A* is classic, if we want to go this way (10:41:45) hiker: nod (10:42:08) hiker: well, maybe (10:42:14) hiker: A* is graph based, right? (10:42:17) Auria: yes (10:42:32) hiker: So if we have a large open arena with only a few sectors, it won't be good enough (10:42:40) hiker: Maybe ... not sure (10:43:01) Auria: well it should be a strategy like, pick a nearby box, do pathfinding, go pick the box. then pick a kart, run after the kart (10:43:13) Auria: hmm this was not clear ^^ (10:43:18) Auria: first "pick" as in "randomly choose" (10:43:23) Auria: second "pick" as in "collect" (10:43:30) hiker: nod (10:43:32) hiker: I understood (10:43:50) Auria: if we go this way then classic pathfinding does it just fine (10:43:51) hiker: Not randomly, but 'somehow' chose a box (e.g. depending on direction it is travelling) (10:43:58) Auria: agreed, what I meant (10:44:13) Auria: (well at "Easy" to could be clueless and pick any) (10:44:19) Auria: s/to/they could be/ (10:44:50) hiker: I just mean that we need some kind of algorithm to handle the steering better. (10:45:16) hiker: If we only have one large quad between us and the target (10:45:25) hiker: Then steering towards the center of the quad is not good enough (10:45:43) hiker: On the other hand, steering towards the target doesn't work either (obstacle in the way) (10:45:45) Auria: agreed, in any case we need togo beyond the graph (10:46:09) hiker: That's what I meant ;) (10:46:13) Auria: I would be tempted to go with a combination of path finding, and then when you are close enough, switch to "drive straight towards" mode (10:46:19) hiker: nod (10:46:23) hiker: Similar to the rubber ball. (10:46:34) hiker: Oh yes, we could reuse the interpolation code in the rubber ball (10:46:49) Auria: good idea (10:46:56) hiker: That might work well enough

supertuxkart-sourceforge-migration / stk-migration-test2

Create AI for Battle Mode #456