go_away

Author Topic: matrices in C, undetermined size?  (Read 3640 times)

0 Members and 1 Guest are viewing this topic.

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,653
  • Helpful? 169
    • Society of Robots
matrices in C, undetermined size?
« on: June 23, 2007, 09:52:10 AM »
Is there a way to create matrices in C of undetermined size? I know its possible in some languages, but Im thinking no for C . . .

Offline ed1380

  • Supreme Robot
  • *****
  • Posts: 1,478
  • Helpful? 3
Re: matrices in C, undetermined size?
« Reply #1 on: June 23, 2007, 01:21:35 PM »
Problems making the $50 robot circuit board?
click here. http://www.societyofrobots.com/robotforum/index.php?topic=3292.msg25198#msg25198

Offline razvanc_roro

  • Jr. Member
  • **
  • Posts: 41
  • Helpful? 0
Re: matrices in C, undetermined size?
« Reply #2 on: June 23, 2007, 03:51:10 PM »
I think you can declare a matrice of undetermined size and border it iterativelly:

you can initilize a 1x1 matrice (a[1][1]="give value/initilize") and then, when ever you need you can choose by border it with 1 column or one row or both...
if there was a matrice a[m][n] by now,
if <condition> then for (j=1,n+1) and (i=1,m+1) a[m+1][j]="give value/initilize" , a[.i][n+1]="give value/initilize" (this is for both row and column). You get it...

PS: 1) Hope that I understood what you wanted to say :D
      2) [.1] > the "." is for the unITALIC code of the editor :)
Cheers!
« Last Edit: June 23, 2007, 03:53:52 PM by razvanc_roro »
Try do your best without doing anything! Possible?!?

Offline rgcustodio

  • Robot Overlord
  • ****
  • Posts: 217
  • Helpful? 0
  • Use "Search" and ye might find answers!
Re: matrices in C, undetermined size?
« Reply #3 on: June 23, 2007, 04:00:08 PM »
Nope you can't make a matrix of undetermined length in C at compile time. BUT, you can dynamically allocate memory during runtime! You will have to deal with pointers and dynamic memory allocation. The big issue is that MCUs (like the AVR) do not have large RAM (most have 1024 bytes only). I think avrlibc supports malloc/free APIs but I haven't personally used them.

I think you can declare a matrice of undetermined size and border it iterativelly:

you can initilize a 1x1 matrice (a[1][1]="give value/initilize") and then, when ever you need you can choose by border it with 1 column or one row or both...

A user can not control the placement of a variable in memory. So if you have several variables and you implement the above procedure you risk running over memory (buffer overrun) that is supposed to be owned by another variable. To properly utilize the above technique the user must be able to place the matrix at a memory location where the user is assured that it'll not hit used memory locations.

For roro's suggestion to work one will have to use a big array and a pointer. N x N matrices are just one big chunk of contiguous memory. One can simulate an N x N matrix by using the big array. And using pointer arithmetic to access the correct memory location. One can write functions to simplify these operations.

Code: [Select]
int myarray[100];
int *p = NULL;

/* simulate a 2 x 50 matrix */
// access first 50 bytes
p = myarray[0]; // like saying n[0][0]
*p = 100;
p = myarray[1]; // like saying n[0][1]
*p = 101;
p = myarray[48]; // like saying n[0][48]
*p = 148;

// access second 50 bytes
p = myarray[50]; // like saying n[1][0]
*p = 100;
p = myarray[51]; // like saying n[1][1]
*p = 101;

It is not a matrix of undetermined size.
« Last Edit: June 23, 2007, 04:36:52 PM by rgcustodio »
The best thing one can do when it's raining is to let it rain. - H. W. Longfellow

understanding is the path to enlightenment

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,653
  • Helpful? 169
    • Society of Robots
Re: matrices in C, undetermined size?
« Reply #4 on: June 23, 2007, 04:36:38 PM »
So the reason I asked is that Im doing robot mapping in an unknown area and just wanted my map to get bigger only when it needed to.

I guess it might be easier to just define a map large enough to fill the rest of my unused memory instead . . .

Offline rgcustodio

  • Robot Overlord
  • ****
  • Posts: 217
  • Helpful? 0
  • Use "Search" and ye might find answers!
Re: matrices in C, undetermined size?
« Reply #5 on: June 23, 2007, 04:42:15 PM »
I guess it might be easier to just define a map large enough to fill the rest of my unused memory instead . . .

Maybe... but don't use all of the seemingly unused memory. When a function or an interrupt service routine is called the compiler automagically generates code to save registers in the system stack which is in the main memory! If you have no more space because you alloted it to your matrix you'll have problems properly running your program.
The best thing one can do when it's raining is to let it rain. - H. W. Longfellow

understanding is the path to enlightenment

Offline Nyx

  • Robot Overlord
  • ****
  • Posts: 204
  • Helpful? 0
Re: matrices in C, undetermined size?
« Reply #6 on: June 23, 2007, 07:54:56 PM »
So the reason I asked is that Im doing robot mapping in an unknown area and just wanted my map to get bigger only when it needed to.

I guess it might be easier to just define a map large enough to fill the rest of my unused memory instead . . .

You could do that using a graph structure, creating nodes for explored areas only. This is rather easy to do. Your graph can be grid-like if you want, and nodes can still have cartesian coordinates. This has the advantage that expanding your map is a painless process...

If you do this with a matrix, the most common approach is to double the matrix dimensions along one axis, by allocating a new matrix twice the size, and copying the data over. This may be slow, and may create an unpleasing "pause" depending on how much data needs to be copied... It also has the disadvantage that you may be allocating much more memory than you really need. With the matrix approach, no matter what you do, the only way to resize the matrix is to reallocate it, which will always be slow.

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,653
  • Helpful? 169
    • Society of Robots
Re: matrices in C, undetermined size?
« Reply #7 on: June 23, 2007, 08:31:51 PM »
Nyx, thats what I was thinking originally.

But Im not even sure if I want cartesian coordinates cause my robot is roaming around my house . . . its not a perfect 90 degree angle maze . . . and I dont really trust any encoders either since my floor is much less than ideal . . .

Ive been working on a map system that uses radial coordinates (why not, a scanner returns radial data, no?). This would give me high precision close to the robot and low precision far away (more ideal, anyway).

Its still an idea in progress, but I got some code written for it today. Im still deciding how to have the robot keep track of where it is globally . . . probably with a camera and colored LED beacons . . .

Offline sdk32285

  • Supreme Robot
  • *****
  • Posts: 418
  • Helpful? 0
Re: matrices in C, undetermined size?
« Reply #8 on: June 23, 2007, 09:37:56 PM »
For global pose an IMU would be good however good ones are very expensive. The cheapest one that i have used is the http://microstrain.com/3dm-gx1.aspx which costs about $1000 (if you don't get developers kit) the downside is that the accelerometers has about 15 deg/hour drift. Decent ones with <1 deg/hour drift can cost $25K.

Depending on the floor you can use a small low friction caster wheel with an encoder
Robots for Roboticists Blog - http://robotsforroboticists.com/

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,653
  • Helpful? 169
    • Society of Robots
Re: matrices in C, undetermined size?
« Reply #9 on: June 23, 2007, 10:15:36 PM »
Quote
Depending on the floor you can use a small low friction caster wheel with an encoder

My floor has multiple surface types: tile, carpet, and wood. And its always getting dirty with all my housemates runnin around . . . Basically there is no way encoders can be entrusted to work with all the various slip conditions. :-\

IMU's always drift . . . in the end I will still need some type of external reference . . . like SLAM or the beacon idea . . . and I think Im too noob-ish to pull off SLAM with a microcontroller . . . :P

I think Im just gonna use the rangefinder to follow walls and avoid objects, while using the cam + beacons as a global reference. I went looking through my old boxes and it turns out I own 3 CMUcams (I didnt even know I had that many! :o). I also just found some CMUcam with ATmega8 source code, so it wont be long before I get stuff up and working . . .

Today I just bought $100 worth of bluetooth stuff to do wireless with my robot, perhaps I can get my PC to process stuff . . . but no idea how yet, never done this before . . .

Offline JesseWelling

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 707
  • Helpful? 0
  • Only You Can Build A Robot!
Re: matrices in C, undetermined size?
« Reply #10 on: June 24, 2007, 05:37:51 AM »
....gumstix... ;)

Offline AdminTopic starter

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,653
  • Helpful? 169
    • Society of Robots
Re: matrices in C, undetermined size?
« Reply #11 on: June 24, 2007, 08:06:26 AM »
Quote
....gumstix...

ehhhh I dont like the pinouts of it . . . plus it still uses AVR . . .

For now, just so we all have a common platform in my tutorials, Im sticking with the $50 Robot microcontroller . . .

btw, for those who dont know, I upgraded it to a more powerful ATmega168

I had run low on memory . . .

Offline JesseWelling

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 707
  • Helpful? 0
  • Only You Can Build A Robot!
Re: matrices in C, undetermined size?
« Reply #12 on: June 24, 2007, 10:18:49 PM »
You mean the whole ARM and AVR for the two layer approach thing? I'm a bit conffused because I was always told ATMegas are AVRs...

Any who...I'm putting together a quick tutorial on the whole 2d array thing... maybe have it done on friday?

 


Get Your Ad Here