0

I'm recreating a game called "Bubble Blast 2" (found on the Play Store, you can watch it on YT) in C using the ncurses library. I've already coded the physics of the game and I need a code that will calculate the fewest moves to solve the game.
Everything in the game is saved in a struct and I need to also use it to calculate the moves in the recursive function.
The struct is modified by the game physics as the game goes.
The recursive function must (at least I think) use the same game physics code (that modifies the struct).

So how can I use the struct in the recursion if it gets modified by the game physics?

This is the game struct:

struct game;

typedef struct point {
  int x;
  int y;
} POINT, *POINT_P;

typedef struct bubble {
  POINT point;
  int state;
} BUBBLE, *BUBBLE_P;

typedef struct bubbles {
  BUBBLE* bubbles;
  int length;
  int allocated;
} BUBBLES, *BUBBLES_P;

typedef struct projectile {
  POINT point;
  char direction;
  int restoreChar;
  int restoreColor;
} PROJECTILE, *PROJECTILE_P;

typedef struct projectiles {
  PROJECTILE* projectiles;
  int length;
  int allocated;
} PROJECTILES, *PROJECTILES_P;

typedef struct game {
  BUBBLES bubbles;
  PROJECTILES projectiles;
  int rows;
  int columns;
  int selected;
  int array[6][5];
  int moves;
  int minMoves;
  bool finished;
  bool movesCalc;
} GAME, *GAME_P;

I don't think the rest of the code is needed because it's just the physics of the game and you just need to know that it modifies the struct as the you play the game, but I might be wrong, if you think more code would help tell me and I'll add it as soon as possible.

Jackrin
  • 83
  • 3
  • 8
  • You have forgotten to ask a question. – John Bollinger Jun 03 '22 at 13:45
  • Ok, how about a question that's a little more specific? It is utterly routine for recursive functions to modify the data provided to them. What is it about the details of your particular case that has you concerned? – John Bollinger Jun 03 '22 at 13:51
  • @JohnBollinger I'll try to explain. the way I was thinking about the recursion was like this: I start from the first bubble, then I let the engine run to see the effects on the struct, then I go with either the same bubble if it didn't pop, or with the next available bubble. But when the engine modifies the struct it stays modified right? And then when the recursion needs to go "back", it doesn't have an unmodified version of the struct. Sorry if it's contorted but i've never had to do a recursion as complicated as this one and i'm not really sure how to do it. – Jackrin Jun 03 '22 at 13:57
  • 2
    @Jackrin, Aside: Style issues: consider 1) not using all upper case in type names 2) not type-defining pointers in this code 3) avoid naked magic numbers like 5,6. Use a macro: `#define ARRAY_COLUMN 5`. – chux - Reinstate Monica Jun 03 '22 at 14:02
  • @chux-ReinstateMonica What do you mean by "not using all upper case". And I don't really know what you mean by the second point. But I didn't ask for comments on my struct code, that is just for people to see how it's structured. – Jackrin Jun 03 '22 at 14:06
  • You have a game state (structures), and you want to produce some simulation on that game state to find the "best solution", then, let the game "playing". your problem is that you use the same "engine" to simulate, than the one to "let playing", so the "simulation" actualy change the game state. Am I correctly understanting ? –  Jun 03 '22 at 14:11
  • @Jackrin What do you mean by "not using all upper case". --> Type `PROJECTILES` name uses all upper case letters. Consider something more readable and less shouting like `Projectiles`. "... is just for people to see how it's structured" is easier to read that way and then to offer ideas. – chux - Reinstate Monica Jun 03 '22 at 14:12
  • 2
    @Jackrin "don't really know what you mean by the second point." --> Review [Is it a good idea to typedef pointers?](https://stackoverflow.com/q/750178/2410359). – chux - Reinstate Monica Jun 03 '22 at 14:14
  • @Sedenion basically i created the engine that runs while you play a normal game, and during a normal game it creates an unspecified number of projectiles that get added and removed from the array of projectiles. I wanted to calculate the moves using the same engine because of consistency with the physics and also i don't think there's any other way. The problem was that when the recursion needs to go back, let's say from the branch "1->1->1" to the branch "1->1->2", before testing "2" it needs to have a prior version to when "1" was tested. – Jackrin Jun 03 '22 at 14:22

2 Answers2

1

So how can I use the struct in the recursion if it gets modified by the game physics?

A struct is a object like int is an object. You can use recursion the same way.

void foo(object bar) {
  bar.member = new_value();
  if (condition) {
    foo(bar);
  }
}

Not highly efficient to copy a struct, but to improve that, we need more program details.

chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
1

I take the question to be how to handle a situation in which you want to both retain the game state unchanged and perform a simulation that modifies the game state. In that case, the fact that the simulation involves recursion is largely immaterial.

At the level of generality of the question, there are two possible solutions:

  1. Make a copy of the game state for the simulation to use. This copy might or might not need to be complete, depending on the details of the simulation and state. In the recursive case, you might or might not need to make an additional copy when you recurse, depending, again, on the details of the simulation and state. (Equivalently: make a backup of the game state, and restore it after the simulation is complete.)

  2. Write the simulation to revert the changes it makes before it returns.

John Bollinger
  • 160,171
  • 8
  • 81
  • 157
  • So let's imagine that I test the branch "1->1" and then I want to test "1->2". I would need to take a copy of the struct before "1->1" was tested and save it so that it's now a local variable? Also how computationally expensive would this be? – Jackrin Jun 03 '22 at 14:46
  • @Jackrin, very likely yes, there would be a local variable involved in retaining a copy of the state. It's unclear, however, whether just a copy of the `struct game` would be sufficient. Since such an object contains pointers to other objects, it might be necessary to make copies of those too (a "deep copy"). I cannot speak in quantitative terms about how expensive it would be to make such a copy. Probably not too much so if the state is overall smallish and a shallow copy suffices, but this is the sort of thing you need to test. – John Bollinger Jun 03 '22 at 15:00
  • @Jackrin, note also that if you are willing to put upper bounds on the allowed numbers of bubbles and projectiles then you can remove dynamic allocation from consideration (probably a performance win) and simultaneously moot the question of deep *vs* shallow copying. – John Bollinger Jun 03 '22 at 15:04
  • Ok I'll try and see what I can do with this solution. Could you also explain what you meant by the second solution tho cause i'm curious? – Jackrin Jun 03 '22 at 15:04
  • Right now i'm using dynamic allocation for the projectiles but i could also set an upper bound i didn't think about it. Bubbles already are of fixxed size – Jackrin Jun 03 '22 at 15:06
  • @Jackrin, your bubbles may be a fixed size, but your data structures don't say that to me. In any event, the idea with upper bounds would be that `struct bubbles` would directly contain an array of `struct bubble` instead of pointing to an external array (whether dynamically allocated or not). Similarly for `struct projectiles`. In that case, you could make a complete copy of the entire game state via a single, ordinary structure assignment. – John Bollinger Jun 03 '22 at 15:11
  • Ok i see what you mean. I can definitely change the bubbles as you said because they are always 30 (popped bubbles are still there but with state = 0). But i'm not really sure about the projectiles, it would basically destroy all of my code that manages them i think. The way i go through the array is by updating the lenght everytime I add or remove one from the game. I'm not completely against rewriting some of it, if by doing so i save myself from a greater problem, but still not a pleasant choice. – Jackrin Jun 03 '22 at 15:24