random number

[hmpf]

nijntje schrieb:

srand(time(0));
int v[N] = { 0 };   //Array mit Geschwindigkeiten 0=keine Geschwindigkeit
int car[VEHICLE] = { 0 };    //Array mit Position der Fahrzeuge
int N = 30;         //z.B.
int VEHICLE = 7;   //bei 4 funktionierts noch
int V_MAX = 6;
int done = 0;
int count = 0;

Mal eine Zwischenfrage: Stehen die Definitionen der Arrays genau so auch in deinem Quelltext? Und was meinst du mit "mein Code funktioniert nicht"? Bitte etwas genauer werden.

[nijntje]

#include <iostream>
#include <cstdlib>
#include <fstream>

using namespace std;

const int N = 30;	//number of cells
const int V_MAX = 6;	//maximum velocity
const int VEHICLE = 8;	//number of cars

void initial (int, int*, int*);

int main () 
{	
    srand(33);			//set random generator (time(NULL))

	int v[N] = { 0 };	//speed of each vehicle on cell j
	int car[VEHICLE] = { 0 };		//cellnumber of vehicle number i
	int speed_car[VEHICLE] = { 0 };		//speed of car i
	int i;

	for (i=0; i<VEHICLE; i++)  
		initial(i, v, car);	
return 0;
}

void initial (int i, int *v, int *car)		
{
	int done = 0;
	int count = 0;

	while (!done) 
	{
		int b = rand() %N;				//generate number between 0 and 299 for position (array starts with 0)
		int j = b;					//j is the position
		cout << "j= " << j << endl;

		for (int k=0; k<VEHICLE; k++)	//multiple numbers are possible
		{
			if (j != car[k]) 
				count++;
		}

		if (count == VEHICLE)			//in order that array gets full 
		{
			int a = rand() % (V_MAX);	//generate number between 0 and 5 for velocity
			v[j] = a + 1;			//assign a velocity to each car (v+1, because no car is zero and zero velocity is 1)
			car[i] = j;
			done = 1;
		}

	}
	return;						
}

Also wenn VEHICLE so wie hier gross ist im Vergleich zu N, dann muss ich das Terminal gewaltsam beenden. Mit cout lasse ich mir die Zufallszahlen zur Kontrolle ausdrucken, diese werden dann endlos ausgegeben. Ist VEHICLE klein (z.B 3), dann bekomme ich die gewünschten Zufallszahlen.

[SeppJ]

Das hat nichts mit Zufallszahlen zu tun, dein Algorithmus ist schlichtweg falsch. Falls du die Bedingung count == VEHICLE verpasst, dann hat die Schleife keine Chance mehr, jemals zu beenden.

Wenn man nun wusste, was dein Programm überhaupt genau machen soll, könnte man die vielleicht sogar helfen, aber du machst da ja anscheinend ein Geheimnis raus. Und aus dem Programm selbst wird man dank verwirrender Bezeichner auch nicht schlau.

[nijntje]

Ich dachte ich hätte das ganz am Anfang beschrieben. sogar im Code steht was ich mache.
Eigentlich ganz simpel:
Auf N Zellen (einspurige Strasse) zufällig Fahrzeuge (VEHICLE) mit zufälliger Anfangsgeschwindigkeit setzen.
Da ich noch Anfängerin bin, ist klar, dass nicht alles perfekt ist. Was ist genau verwirrend?

[SeppJ]

Irgendwelche Nebenbedingungen? Z.B. darf eine Zelle mehrfach besetzt sein? Bist du dir sicher mit dem Design, also Position und Geschwindigkeit der Autos getrennt zu halten und eine Zellenliste mit den Geschwindigkeiten zu haben? Ich finde das ungewöhnlich.

Was ist genau verwirrend?

Zum Beispiel, dass VEHICLE die Anzahl der Fahrzeuge ist und car die Position der Fahrzeuge.

[nijntje]

Nein, keine Nebenbedingungen. Die Zellen haben die Grösse, die ein Auto in einer Stausituation annehmen würde.

Ja, ich bin mir sicher mit dem Design, ich habe eigentlich schon alles implementiert. Man kann das sicher viel geschickter machen, aber dafür bin ich noch zu unerfahren.
Erst beim Ändern der Anzahl Zellen bzw. Fahrzeuge habe ich diesen Fehler in der Initialisierung bemerkt.

[SeppJ]

Ich zeige dir mal,wie man so etwas machen kann:

// so, machen wir das mal objektorientiert:

// Zunächst mal machen wir, dass Car/vehicle auch wirklich ein
// Auto sind und keine Geschwindigkeit. Aber sie haben eine
// Geschwindigkeit. 

class Car
{
  int speed;
};

// Einer Zelle kann ein Auto zugeordnet sein oder auch nicht.
class Cell
{
  Car *car;
};

// Eine Straße besteht aus vielen Zellen. Ich nehme mal periodische 
// Randbedingungen an. Damit wir die nicht von alleine ausrechnen müssen
// nehmen wir einen Ringpuffer. Da du vermutlich da drauf stehst, das Rad
// zum 543737377ten Mal neu zu erfinden, schreiben wir unseren eigenen:
#include "circular_buffer.h"
class Street
{
  CircularBuffer<Cell> cells;
};

circular_buffer.h:

#ifndef CIRCULAR_BUFFER_H
#define CIRCULAR_BUFFER_H

// Wir schreiben natürlich nicht alles selbst. Die Haupt-
// arbeit übernimmt vector. Wir rechnen bloß die Indizes um.
#include <vector>

// Da wir nur einen Bruchteil der Funktionalität brauchen,
// machen wir mal kein vollständiges STL-kompatibles Interface.
// Wenn wir ambitioniert sind, können wir das nachholen, dann
// kann man den Puffer auch für andere Dinge benutzen.
template<class ElementType> class CircularBuffer
{
  std::vector<ElementType> data;
 public:
  // Als öffentliches Interface brauchen wir bloß Zugriffe und
  // die Größe.
  std::size_t size() const { return data.size(); }
  const ElementType& operator[](std::size_t pos) const
  { return data[pos % size()]; }
  ElementType& operator[](std::size_t pos)
  { return data[pos % size()]; }

  // Außerdem einen Konstruktor, bei dem wir die Größe angeben
  // können
 CircularBuffer(std::size_t size): data(size) {}

  // Und zu guter letzt ein paar Iteratoren, damit wir schöne
  // Algorithmen schreiben können
  class iterator
  {
    CircularBuffer &buf;
    std::size_t pos;
  public:
    // Auch hier ein sehr abgespecktes Interface
    ElementType& operator*() const { return buf[pos]; }
    ElementType* operator->() const { return &buf[pos]; }
    iterator& operator++() { ++pos; return *this; }
    iterator& operator+=(std::size_t rhs) 
      { pos += rhs; return *this; }
    explicit iterator(CircularBuffer const& buf, std::size_t pos=0)
      : buf(buf), pos(pos) {}
  };
  class const_iterator
  {
    CircularBuffer &buf;
    std::size_t pos;
  public:
    // Auch hier ein sehr abgespecktes Interface
    const ElementType& operator*() const { return buf[pos]; }
    const ElementType* operator->() const { return &buf[pos]; }
    const_iterator& operator++() {pos = (pos+1) % buf.size(); return *this;}
    const_iterator& operator+=(std::size_t rhs) 
      { pos = (pos+rhs) % buf.size(); return *this; }
    explicit const_iterator(CircularBuffer const& buf, std::size_t pos=0)
     : buf(buf), pos(pos) {}
  };
};

template<class ElementType> 
const CircularBuffer<ElementType>::iterator
operator+(CircularBuffer<ElementType>::iterator const &lhs, std::size_t rhs)
{ 
  CircularBuffer<ElementType>::iterator tmp(lhs);
  tmp += rhs;
  return tmp;
}

template<class ElementType> 
const CircularBuffer<ElementType>::const_iterator
operator+(CircularBuffer<ElementType>::constiterator const &lhs, std::size_t rhs)
{ 
  CircularBuffer<ElementType>::const_iterator tmp(lhs);
  tmp += rhs;
  return tmp;
}

// So, das sollte eigentlich schon reichen.

#endif

Zurück zum Hauptprogramm. Wie müssen irgendwie simulieren. Dazu müssen alle Objekte einen Zeitschritt weiter. Wir gehen das ganze von unten nach oben an und so sollte man das auch lesen:

// Das Include kommt nach oben, wie es sich gehört.
// Außerdem müssen die anderen Klassen auch sehen,
// wie ein Iterator aussieht.
#include "circular_buffer.h"
// Damit wir nicht so viel schreiben müssen, machen wir einen typedef.
// Das ist auch gut, wenn sich herausstellt, dass unsere Containerwahl
// nicht gut war.
typedef CircularBuffer<Cell> CellsType;

class Car
{
  int speed;
  // Führe eine Maximalgeschwindigkeit ein. Zunächst
  // einmal global. Vielleicht wird das später mal
  // für jedes Auto individuell.
  static int max_speed = 10;
public:
  void drive_forward(CellsType::iterator it)
  {
    // Auto fährt um bis zu speed Zellen weiter
    // Wenn in der Zelle vor ihm ein Auto ist,
    // wird gebremst. Wenn ungebremst gefahren wurde,
    // wird beschleunigt bis zur Maximalgeschwindigkeit.

  }
};

class Cell
{
  Car *car;
public:
  void advance_timestep(CellsType::iterator it)
  {
    // Wenn die Zelle ein Auto hat, dann soll das Auto weiterfahren
    if (car)
      {
        Car *old_car = car;
        car = 0; // Das Auto verlässt die Zelle
        old_car->drive_forward(it); // Und fährt weiter
      }
  }
};

#include "circular_buffer.h"
class Street
{
  CellsType cells;

public:
  // Nun der Kern der Simulation. Die Straße aktualisiert die Zellen
  void advance_timestep()
  {
    for (CellsType::iterator it = cells.begin(); it != cells.end(); ++it)
      {
        it->advance_timestep(it);
      }
  }
};

Nun laufen wir in ein Problem, da wir unser Projekt nicht sauber modularisiert haben, sondern alles in eine Datei geschrieben haben. Die Autos brauchen zum Update Zugriff auf die Methoden der Zellen. Teile daher das Projekt nun Deklarationen und Implementierung auf. Vorher compileren wir einmal, um zu sehen, ob wir was falsch gemacht haben:

[b]$> g++ test.cc -Wextra -Wall -Weffc++[/b]
In file included from test.cc:4:
circular_buffer.h:63: error: expected initializer before ‘operator’
circular_buffer.h:72: error: expected initializer before ‘operator’
test.cc:8: error: ‘Cell’ was not declared in this scope
test.cc:8: error: template argument 1 is invalid
test.cc:8: error: invalid type in declaration before ‘;’ token
test.cc:16: error: ISO C++ forbids in-class initialization of non-const static member ‘max_speed’
test.cc:18: error: ‘CellsType’ is not a class or namespace
test.cc:18: error: expected ‘,’ or ‘...’ before ‘it’
test.cc:18: warning: unused parameter ‘iterator’
test.cc:34: error: ‘CellsType’ is not a class or namespace
test.cc:34: error: expected ‘,’ or ‘...’ before ‘it’
test.cc: In member function ‘void Cell::advance_timestep(int)’:
test.cc:41: error: ‘it’ was not declared in this scope
test.cc: At global scope:
test.cc:34: warning: unused parameter ‘iterator’
test.cc: In member function ‘void Street::advance_timestep()’:
test.cc:58: error: expected initializer before ‘it’
test.cc:58: error: ‘it’ was not declared in this scope
test.cc:58: error: request for member ‘end’ in ‘((Street*)this)->Street::cells’, which is of non-class type ‘CellsType’

Ahh, ja:

circular_buffer.h:63: error: expected initializer before ‘operator’
circular_buffer.h:72: error: expected initializer before ‘operator’

Bei den Operatoren haben wir vergessen, dass wir typename vor von Templates abgeleitete Typen schreiben müssen. Passiert. Einfach nachtragen. Aber eigentlich brauchen wir sowieso keine Konvertierungen. Daher ab als Memberfunktion, das spart Platz und Scherereien mit der Argumentenauflösung.

test.cc:8: error: ‘Cell’ was not declared in this scope
test.cc:8: error: template argument 1 is invalid
test.cc:8: error: invalid type in declaration before ‘;’ token

Eine Äußerung des angesprochenen Problems.

test.cc:16: error: ISO C++ forbids in-class initialization of non-const static member ‘max_speed’

Ups, klar, das muss const sein.

[...]

Viele Folgefehler.

test.cc:58: error: request for member ‘end’ in ‘((Street*)this)->Street::cells’, which is of non-class type ‘CellsType’

Und beim Ringpuffer haben wir begin und end vergessen. so, dann sortieren wir mal um. Außerdem werden wir die const_iteratoren niemals brauchen, daher kürze ich sie raus. Dann sieht das so aus und compiliert wunderbar, tut aber noch nix:

#ifndef CIRCULAR_BUFFER_H
#define CIRCULAR_BUFFER_H

#include <vector>

template<class ElementType> class CircularBuffer
{
  std::vector<ElementType> data;
 public:
  std::size_t size() const { return data.size(); }
  const ElementType& operator[](std::size_t pos) const
  { return data[pos % size()]; }
  ElementType& operator[](std::size_t pos)
  { return data[pos % size()]; }

 CircularBuffer(std::size_t size): data(size) {}

  class iterator
  {
    CircularBuffer &buf;
    std::size_t pos;
  public:
    ElementType& operator*() const { return buf[pos]; }
    ElementType* operator->() const { return &buf[pos]; }
    iterator& operator++() { ++pos; return *this; }
    iterator& operator+=(std::size_t rhs) 
      { pos += rhs; return *this; }
    // Noch ein kleiner Fehler hier, Referenz darf nicht const sein
    explicit iterator(CircularBuffer & buf, std::size_t pos=0)
      : buf(buf), pos(pos) {}
    // Und den Operator != vergessen
    bool operator!=(const iterator& rhs)
    { return &buf != &rhs.buf or pos != rhs.pos; }
    const  iterator operator+(std::size_t rhs) const
    { iterator tmp(*this); tmp += rhs; return tmp; }
  };

  iterator begin() { return iterator(*this); }
  iterator end() { return iterator(*this, size()); }
};

#endif

#include "circular_buffer.h"

class Cell;
typedef CircularBuffer<Cell> CellsType;

class Car
{
  int speed;
  static const int max_speed = 10;
public:
  void drive_forward(CellsType::iterator it);
};

class Cell
{
  Car *car;
public:
  void advance_timestep(CellsType::iterator it);
};

class Street
{
  CellsType cells;
public:
  void advance_timestep();
};

void Car::drive_forward(CellsType::iterator it)
{
}

void Cell::advance_timestep(CellsType::iterator it)
{
  // Wenn die Zelle ein Auto hat, dann soll das Auto weiterfahren
  if (car)
    {
      Car *old_car = car;
      car = 0; // Das Auto verlässt die Zelle
      old_car->drive_forward(it); // Und fährt weiter
    }
}

void Street::advance_timestep()
{
  for (CellsType::iterator it = cells.begin(); it != cells.end(); ++it)
    {
      it->advance_timestep(it);
    }
}

Eigentlich würde man ja stärker in einzelne Dateien trennen, aber das kommt im Forum nicht gut.

So, nun kann man den eigentlichen Algorithmus implementieren. Außerdem noch ein bisschen Boilerplatecode:

#include "circular_buffer.h"

class Cell;
typedef CircularBuffer<Cell> CellsType;

class Car
{
  int speed;
  static const int max_speed = 10;
public:
  void drive_forward(CellsType::iterator it);
  Car(int speed = 0);
};

class Cell
{
  Car *car;
public:
  void advance_timestep(CellsType::iterator it);
  bool is_empty() const;
  void set_car(Car* new_car);
  Cell();
};

class Street
{
  CellsType cells;
public:
  void advance_timestep();
  void set_car(Car * car, std::size_t pos);
  Street(std::size_t length);
};

void Car::drive_forward(CellsType::iterator it)
{
  // Suche letztes freies Feld in Reichweite
  for (int current_speed = 0; current_speed <= speed; ++current_speed)
    {
      if (!(it+current_speed+1)->is_empty()) 
        {
          // Im Feld vor uns ist ein Auto. Passe Geschwindigkeit an
          speed = current_speed;
          // Und setze unser Auto auf das Feld davor
          (it+speed)->set_car(this);
          return;
        }
    }
  // Kein anderes Auto gesehen: Umsetzen und Beschleunigen
  (it+speed)->set_car(this);
  if (speed < max_speed) ++speed;
}
Car::Car(int speed): speed(speed) {}

void Cell::advance_timestep(CellsType::iterator it)
{
  // Wenn die Zelle ein Auto hat, dann soll das Auto weiterfahren
  if (car)
    {
      Car *old_car = car;
      car = 0; // Das Auto verlässt die Zelle
      old_car->drive_forward(it); // Und fährt weiter
    }
}
bool Cell::is_empty() const { return !car; }
void Cell::set_car(Car *new_car) {car = new_car;}
Cell::Cell(): car(0) {}

void Street::advance_timestep()
{
  for (CellsType::iterator it = cells.begin(); it != cells.end(); ++it)
    {
      it->advance_timestep(it);
    }
}
void Street::set_car(Car * car, std::size_t pos) {cells[pos].set_car(car);}
Street::Street(std::size_t length): cells(length) {}

Außerdem sollte der Konstruktor des Ringpuffers natürlich explicit sein, wie mir aber erst hier auffiel. So, Zeit ein kleines Testprogramm zu schreiben. Dazu werden noch ein paar Ausgabeoperatoren geschrieben und ein kleines Beispiel aufgesetzt:

// Diese Funktionen sind allesamt Friends der jeweiligen Klasse:
std::ostream& operator<<(std::ostream& out, const Car& rhs)
{ return out << rhs.speed; }

std::ostream& operator<<(std::ostream& out, const Cell& rhs)
{ if (!rhs.is_empty()) out << *rhs.car; else out << ' '; return out; }

std::ostream& operator<<(std::ostream& out, const Street& rhs)
{
  out << '|';
  for(std::size_t i=0; i < rhs.cells.size(); ++i) out << rhs.cells[i];
  out << '|';
  return out; 
}

int main()
{
  std::vector<Car> cars(2);
  Street street(70);
  street.set_car(&cars[0],0);
  std::cout << street << '\n';
  for (int i = 0; i < 10; ++i)
    {
      street.advance_timestep();
      std::cout << street << '\n';
    }
}

So, und nun der große Augenblick, auf den wir alle gewartet haben:

|0                                                                     |
|1                                                                     |
|  9                                                                   |
|    9                                                                 |
|      9                                                               |
|        9                                                             |
| 9                                                                    |
|   9                                                                  |
|     9                                                                |
|       9                                                              |
|9                                                                     |

Das war wohl nix.

Ok, kurz mit dem Debugger drüber. Wenn ein Auto weiterfährt, wird es auch vom Update der nächsten Zelle erfasst, wodurch es immer weiter fährt. Das war auch eine Murksiddee, das so zu machen. Eine Straße fährt kein Auto, ein Auto fährt auf der Straße! Dafür bekommt das Auto nun eine Position. Eigentlich hatte ich das gleich so vor, aber ich wollte mich möglichst an dein ursprüngliches Design halten. Aber das war wohl nicht so gut. Noch ein paar kleine Änderungen am Ringpuffer (zeige ich am Ende) und das Programm sieht so aus:

class Car
{
  int speed;
  CellsType::iterator pos;
  static const int max_speed = 9;
public:
  void drive_forward();
  void hit_the_road();
  Car(int speed, CellsType::iterator pos);
  friend std::ostream& operator<<(std::ostream&, const Car&);
};

class Cell
{
  Car *car;
public:
  bool is_empty() const;
  void set_car(Car* new_car);
  Cell();
  friend std::ostream& operator<<(std::ostream&, const Cell&);
};

class Street
{
  CellsType cells;
public:
  Street(std::size_t length);
  CellsType::iterator get_pos(std::size_t pos);
  friend std::ostream& operator<<(std::ostream&, const Street&);
};

void Car::drive_forward()
{
  pos->set_car(0);
  int current_speed = 0;
  for (; current_speed <= speed; ++current_speed)
    {
      if (!(pos+current_speed+1)->is_empty()) 
        {
          speed = current_speed-1;
          break;  
        }
    }
  pos+=current_speed;
  hit_the_road();
  if (speed < max_speed) ++speed;
}
void Car::hit_the_road() { pos->set_car(this); }
Car::Car(int speed, CellsType::iterator pos): speed(speed), pos(pos) {}

bool Cell::is_empty() const { return !car; }
void Cell::set_car(Car *new_car) {car = new_car;}
Cell::Cell(): car(0) {}

Street::Street(std::size_t length): cells(length) {}
CellsType::iterator Street::get_pos(std::size_t pos) { return cells.begin()+pos; }

std::ostream& operator<<(std::ostream& out, const Car& rhs)
{ return out << rhs.speed; }

std::ostream& operator<<(std::ostream& out, const Cell& rhs)
{ if (!rhs.is_empty()) out << *rhs.car; else out << ' '; return out; }

std::ostream& operator<<(std::ostream& out, const Street& rhs)
{
  out << '|';
  for(std::size_t i=0; i < rhs.cells.size(); ++i) out << rhs.cells[i];
  out << '|';
  return out; 
}

int main()
{
  std::vector<Car> cars;
  Street street(70);
  cars.push_back(Car(7,street.get_pos(0)));
  cars.push_back(Car(0,street.get_pos(5)));

  for (std::size_t i=0; i < cars.size(); ++i)
    cars[i].hit_the_road();

  std::cout << street << '\n';
  for (int i = 0; i < 20; ++i)
    {
      for (std::size_t i=0; i < cars.size(); ++i)
        cars[i].drive_forward();
      std::cout << street << '\n';
    }
}

|7    0                                                                |
|    4 1                                                               |
|     1  2                                                             |
|       2   3                                                          |
|          3    4                                                      |
|              4     5                                                 |
|                   5      6                                           |
|                         6       7                                    |
|                                7        8                            |
|                                        8         9                   |
|                                                 9          9         |
|9                                                          9          |
|          9                                                          9|
|         9          9                                                 |
|                   9          9                                       |
|                             9          9                             |
|                                       9          9                   |
|                                                 9          9         |
|9                                                          9          |
|          9                                                          9|
|         9          9                                                 |

Sieht doch schon sehr gut aus. Aber das gibt nur Kolonnenfahren, deswegen mache ich die Höchstgeschwindigkeit variabel, aber das zeige ich jetzt nicht explizit. Nun zu deiner Ursprungsfrage, wie man so ein System aufsetzen kann. Nun, eigentlich hat sich die Frage durch gutes Design bereits erledigt, weil wir nun trivial Autos auf der Straße verteilen können. Das Ziehen der Positionen entspricht dem Ziehen von N aus M Zahlen ohne Zurücklegen. Da ich aber gerade faul bin, mische ich einfach M Karten und nehme die obersten N. Da das ganze nur einmal am Anfang des Programms geschieht, ist Performance dafür herzlich egal.

#include <algorithm>
#include <ctime>
#include <cstdlib>
using namespace std;
int main()
{
  srand(time(0));
  const size_t street_length = 80;  
  const size_t num_cars = 18;

  std::vector<int> positions(street_length);
  for(size_t i=0; i < street_length; ++i) positions[i]=i;
  random_shuffle(positions.begin(), positions.end());

  std::vector<Car> cars;
  Street street(street_length);
  for(size_t i=0; i < num_cars; ++i)
    cars.push_back(Car(rand()%4,street.get_pos(positions[i]), rand()%4+4));

 // und weiter wie oben

Mal sehen:

|     0     3   2 3 33   10       1    3 3     2  3              33        3 3  3|
|   4  1       3  21   330 1        2      4 4    3   4              44       32 |
|33   2  2       2  22 00 1  2         3        54    4    5              44     |
|   33  2   3      2 11 11  2   3          4        44     5     5             44|
| 33  22   3    4   1 11  22   3    4           5        55      5     5         |
|   22   33    4    41  22   33    4     5            6        66      5     5   |
|  5   33    44    4  22   33    44     4      5             6       66      5   |
|  5  3    44    44  2   33    44     55     4       5              6      66    |
|66      54    44  22   3    44     55     55     4        5               6     |
| 6    66    44  22   33    4     55     55     55     4         5               |
|        6 44  22   33    44     5     55     55     55     4          5         |
|           322   33    44     55     5     55     55     55     4           5   |
|  5           333    44     44     55     5     55     55     55     4          |
|        5         444     55     44     55     5     55     55     55     4     |
|              5        555     55     44     55     5     55     55     55     4|
|    4               5       555     55     44     55     5     55     55     55 |
|  55     4                5      555     55     44     55     5     55     55   |
|55     55     4                 5     555     55     44     55     5     55     |
|     55     55     4                 5     555     55     44     55     5     55|
|   55     55     55     4                 5     555     55     44     55     5  |
|  5     55     55     55     4                 5     555     55     44     55   |

:xmas1:
Das ist doch hübsch. Erst gibt's einen kleinen Stau, dann passen alle ihre Geschwindigkeit an und fahren in Kolonne. So wie man es auf der Autobahn machen sollte. Jetzt müsste man noch spielen und unterschiedlich aggressive Fahrer einbauen, die trotzdem Gas geben. Und mehrere Spuren. Aber das ist dein Projekt. Hier mal das ganze Programm, damit du da drauf aufbauen kannst. Kommentare sind in dieser letzten Fassung größtenteils draußen, in diesem Post ist hoffentlich genug erklärt .

circular_buffer.h (Kein Ruhmesblatt, da fehlte Entwicklungszeit. Nimm vielleicht besser was fertiges):

#ifndef CIRCULAR_BUFFER_H
#define CIRCULAR_BUFFER_H

#include <vector>

template<class ElementType> class CircularBuffer
{
  std::vector<ElementType> data;
 public:
  std::size_t size() const { return data.size(); }
  const ElementType& operator[](std::size_t pos) const
  { return data[pos % size()]; }
  ElementType& operator[](std::size_t pos)
  { return data[pos % size()]; }

  // Dieser Konstruktor sollte explicit sein
 explicit CircularBuffer(std::size_t size): data(size) {}

  class iterator
  {
    // Nehme einen Zeiger, damit man das Objekt trivial kopieren kann
    CircularBuffer *buf;
    std::size_t pos;
  public:
    ElementType& operator*() const { return (*buf)[pos]; }
    ElementType* operator->() const { return &(*buf)[pos]; }
    iterator& operator++() { ++pos; return *this; }
    iterator& operator+=(std::size_t rhs) 
      { pos+=rhs; return *this; }
    explicit iterator(CircularBuffer * buf, std::size_t pos=0)
      : buf(buf), pos(pos) {}
    bool operator!=(const iterator& rhs)
    { return buf != rhs.buf or pos != rhs.pos; }
    const  iterator operator+(std::size_t rhs) const
    { iterator tmp(*this); tmp += rhs; return tmp; }
 };

  iterator begin() { return iterator(this); }
  iterator end() { return iterator(this, size()); }
};

#endif

Und das Hauptprogramm (alles an einem Stück. Naja, nicht gerade übersichtlich, macht es aber dem Compiler einfach zu optimieren, wenn du mal lange Läufe (ohne Ausgabe zwischendrin machst):

#include <iostream>

#include "circular_buffer.h"

class Cell;
typedef CircularBuffer<Cell> CellsType;

class Car
{
  int speed;
  CellsType::iterator pos;
  int max_speed;
public:
  void drive_forward();
  void hit_the_road();
  Car(int speed, CellsType::iterator pos, int max_speed);
  friend std::ostream& operator<<(std::ostream&, const Car&);
};

class Cell
{
  Car *car;
public:
  bool is_empty() const;
  void set_car(Car* new_car);
  Cell();
  friend std::ostream& operator<<(std::ostream&, const Cell&);
};

class Street
{
  CellsType cells;
public:
  Street(std::size_t length);
  CellsType::iterator get_pos(std::size_t pos);
  friend std::ostream& operator<<(std::ostream&, const Street&);
};

void Car::drive_forward()
{
  pos->set_car(0);
  int current_speed = 0;
  for (; current_speed <= speed; ++current_speed)
    {
      if (!(pos+current_speed+1)->is_empty()) 
        {
          speed = current_speed-1;
          break;  
        }
    }
  pos+=current_speed;
  hit_the_road();
  if (speed < max_speed) ++speed;
}
void Car::hit_the_road() { pos->set_car(this); }
Car::Car(int speed, CellsType::iterator pos, int max_speed)
  : speed(speed), pos(pos), max_speed(max_speed) {}

bool Cell::is_empty() const { return !car; }
void Cell::set_car(Car *new_car) {car = new_car;}
Cell::Cell(): car(0) {}

Street::Street(std::size_t length): cells(length) {}
CellsType::iterator Street::get_pos(std::size_t pos) { return cells.begin()+pos; }

std::ostream& operator<<(std::ostream& out, const Car& rhs)
{ return out << rhs.speed; }

std::ostream& operator<<(std::ostream& out, const Cell& rhs)
{ if (!rhs.is_empty()) out << *rhs.car; else out << ' '; return out; }

std::ostream& operator<<(std::ostream& out, const Street& rhs)
{
  out << '|';
  for(std::size_t i=0; i < rhs.cells.size(); ++i) out << rhs.cells[i];
  out << '|';
  return out; 
}

#include <algorithm>
#include <ctime>
#include <cstdlib>
using namespace std;
int main()
{
  srand(time(0));
  const size_t street_length = 80;  
  const size_t num_cars = 18;

  std::vector<int> positions(street_length);
  for(size_t i=0; i < street_length; ++i) positions[i]=i;
  random_shuffle(positions.begin(), positions.end());

  std::vector<Car> cars;
  Street street(street_length);
  for(size_t i=0; i < num_cars; ++i)
    cars.push_back(Car(rand()%4,street.get_pos(positions[i]), rand()%4+4));

  for (std::size_t i=0; i < cars.size(); ++i)
    cars[i].hit_the_road();

  std::cout << street << '\n';
  for (int i = 0; i < 20; ++i)
    {
      for (std::size_t i=0; i < cars.size(); ++i)
        cars[i].drive_forward();
      std::cout << street << '\n';
    }
}

Zu beachten ist noch, dass irgendwann der Index vom Ringpuffer überlaufen wird, da dieser absolut gespeichert wird. Das ist zwar einerseits gut, da du so feststellen kannst, wie viele Runden ein Auto gefahren ist. Aber du kannst das Programm nicht Ewigkeiten durchlaufen lassen - irgendwann hat ein Rechner dann nämlich auch mal ausgezählt. Je nach Maximalgeschwindigkeit müssten bei einem 64-Bit Wert aber mehrere Jahrzehnte drin. Bei einem 32-Bit System wird das aber wesentlich eher überlaufen. Und ich mag gerade nicht analysieren, was dann passiert. Da alles unsigned ist, könnte das sogar gut gehen.

[nijntje]

Wow, vielen dank. Werde mir das morgen nochmal genauer ansehen. Ist ja ein richtiger Kurs. Das hast du dir in dieser zeit schnell aus dem Ärmel geschüttelt?! Super...

[nijntje]

Hallo Seppj

zuerst möchte ich mich nochmal bedanken, dass du dir die zeit genommen hast mir das alles zu erklären.

darf ich dazu nochwas fragen??

aus dem main() am schluss:

for(size_t i=0; i < street_length; ++i) positions[i]=i; 
  random_shuffle(positions.begin(), positions.end()); 

  std::vector<Car> cars; 
  Street street(street_length); 
  for(size_t i=0; i < num_cars; ++i) 
    cars.push_back(Car(rand()%4,street.get_pos(positions[i]), rand()%4+4)); 
  
  for (std::size_t i=0; i < cars.size(); ++i) 
    cars[i].hit_the_road();

woher hast du dieses random_shuffle?
kann ich das immer nehmen, wenn ich zufallszahlen brauche (ohne zurücklegen)?

was meinst du mit hit_the_road?

und:

cars.push_back(Car(rand()%4,street.get_pos(positions[i]), rand()%4+4));

hier verstehe ich eigentlich die ganze zeile nicht.
(wieso modulo4, woher kommt push_back)

grüsse
nijntje

[314159265358979]

push_back ist eine Memberfunktion von std::vector, sie fügt ein Element hinten an. random_shuffle, oder mit vollem Namen std::random_shuffle ist ein Algorithmus aus der Standardbibliothek, der einen Bereich von Elementen zufällig mischt.

[SeppJ]

Die magische Zahl 4 ist nur für das Beispiel. Ich möchte eine Anfangsgeschwindigkeit von 0 bis 3 und eine Maximalgeschwindigkeit von 4 bis 7. Das kamen mir wie gute Werte für ein übersichtliches Beispiel vor.

Die hit_the_road Funktion macht, dass die Autos sich mal bei der Zelle melden, in der sie gerade sind. Meinetwegen sei in jeder Zelle ein Sensor, so könnte man das erklären. Zweck der Geschichte ist, dass man dann die Straße in einem Rutsch zeichnen kann, anstatt erst die Straße und dann die Autos da drauf, wie es natürlicher wäre. Aber das zeichnen von Autos an eine bestimmte Position ist in C++ etwas, was über ein schnelles Beispielprogramm hinausgeht, daher habe ich das nicht so gemacht. Außerdem kann man so die Kollisionsabfrage sehr vereinfachen, da man gucken kann, ob die Zelle vor dem Auto frei ist, anstatt zu gucken, welches Auto vor einem fährt und wie weit es noch weg ist.